펭로그

문제 링크 : https://boj.kr/2581 소수는 어떤 수 N의 약수가 1과 자기 자신만 가지는 숫자를 의미한다.소수를 구하는 것은 정말 어렵지만 '판별'은 가능하다.자기 자신보다 작은 정수 중에서 약수가 존재하는지를 2~N까지 반복하면 된다.하지만, 약수는 N의 제곱근 보다 큰 숫자는 절대로 나올 수 없다. N의 제곱근 보다 큰 정수에 어떤 정수를 곱하면 이미 N보다 커지기 때문이다. 따라서 N의 제곱근 범위까지만 구하면 된다.하지만 이 방법은 소수를 판별하는 방법이지 소수를 구하는 방법이 아니다.어떤 범위의 숫자가 주어졌을때 소수인지 아닌지를 판별하려면 1~N의 제곱근 까지 계산해야 하는데 이 것을 주어진 범위만큼 반복해야 하기 때문에 소수 리스트를 미리 구해놓고 구하는 편이 빠른 연산 방법이..