소수 판별하기

백준 1978번을 풀다가 소수에 대해 생각했다.

문제의 핵심은 1000이하의 N개의 숫자가 주어졌을 때 소수의 개수를 새는 것이다.

처음에는 소수의 특징을 파악한 후 각 숫자가 소수인지 아닌지를 판별하는 방법을 써야하나 싶었는데,

소수가 1과 본인을 제외한 수로 나눠지지 않는다는 특징 때문에 위의 방법을 사용하기 어려웠다.

결국 가장 효율적이라고 알려진 '에라토스테네스의 체'라는 방법을 이용해 1000이하의 수 중에서 소수만 리스트에 남기고

입력받은 수 중에 리스트에 포함되있는 수를 세어 결과를 산출했다.

소수를 세기 위한 방법으로는 숫자를 그 이하 모든 수로 나눠 떨어지는지 확인하는 방법을 가장 쉽게 생각할 수 있다.

이를 더 효율적으로 하기 위해 소수가 아닌 수는 결국 곱으로 나타낼 수 있고 n의 제곱근을 제곱한 수가 n이라는 수의 특징을 생각해보면

곱으로 나타낼 수 있는 수를 이루는 수들은 sqrt(n)보다 크거나 작은 수를 각각 포함하고 있다.

(이는 예를들어 12 = 2 * 6으로 이뤄져있고 2 root 3보다 큰 수 하나, 작은 수 하나로 이뤄져있음을 알 수 있다.)

에라토스테네스의 체가 효율적으로 소수를 구하는 방법인 이유는 소수가 아닌 수를 지우면서 계산하기 때문이라 추론한다.