[백준] 2581번 - 소수
문제
알고리즘을 공부하다 보면 꼭 거치는 문제이다. 소수는 생각보다 쓰이는 곳이 많아 잘 알고 있어야 한다. 내가 구현할 수 있는 소수를 구하는 방법은 총 3가지이다. 이 방법들 외에도 소수를 확률적으로 판정하는 Solovay-Strassen 알고리즘, Lehmann-Peralta 알고리즘, Miller-Rabin 알고리즘 등이 있는데 나중에 더욱 공부하고 소개하도록 하겠다.
첫 번째로는 그냥 무작정 구하기이다. 이는 매우 무식하고 제일 처음 떠오르는 방법이다. 소수인지 알고싶은 수가 n이라면 그냥 1부터 n까지의 수로 나눠서 나머지가 0인지 아닌지를 판별하면 되기 때문이다. n이 작다면 금방 구하겠지만 n이 커지면 절대 못 써먹을 알고리즘이다. 그러므로 생략하도록 하겠다.
두 번째는 첫 번째의 연장선이라 볼 수 있다. 사실 2를 제외한 짝수는 검사를 할 필요가 없다. 또한 굳이 1부터 n까지의 수로 나눠서 확인해 볼 필요도 없다. 자연수 n이 소수이기 위한 필요-충분조건은 “n이 n의 제곱근보다 크지 않은 어떤 소수로도 나눠지지 않는다”이다. 나누는 과정에서 몫이 발생하게 되는데 몫과 나누는 수, 둘 중 하나는 반드시 sqrt(n) 이하이기 때문이다. 소스 코드로 표현하면 다음과 같다. 시간 복잡도는 O(√N)이다. sqrt(2), sqrt(3)은 자료형이 int라 내림으로 1이 되는 점을 이용하였다. 그 외는 설명 그대로 구현하였다.
마지막으로는 소수를 처음 배울 때 무조건 들어봤던 “에라토스테네스의 체”라는 것이다. 2부터 N-1까지의 수 중, 2부터 시작해서 체에 거르는 것이다. 2를 제외한 2의 배수를 다 지우고, 그 다음 수인 3을 제외한 3의 배수를 다 지우고, 그 다음은 5(4가 아니다 4는 앞서 걸러졌기 때문), 이런 식으로 거듭 반복해서 결국, 체에 걸러지지 않고 남은 수들이 모두 소수가 된다. 모든 자연수는 소수의 곱으로 표현가능하기에 이런 방법이 가능하다. 이 방법을 쓰려면 메모리가 충분한 상황이어야 하며, 범위 안의 수를 모두 구할 때 매우 효과적이다. 범위 안의 모든 수를 구한다면 에라토스테네스의 체가 제일 완전한 방법이라는 것을 꼭!! 기억해두자. 다만 임의의 수가 소수인지를 판별하는 경우는 더 좋은 방법이 매우 많다. 이는 서론에 소개한 알고리즘 등이 있으며, 추후 게재하겠다. 아래는 에라토스테네스의 체를 이용한 소스코드이다.
