[Algorithms] 소수(Prime Number) 판별하는 간단한 방법
알고리즘 문제에서 단골 손님이라고 할 수 있는 소수(Prime Number) 판별하는 방법에 대해서 정말 간단하게 알아보려고 합니다.
평소 저는 소수판별을 하기 위해서 아래 코드와 같은 방법을 사용하였습니다.
bool isPrimeNumber(int targetNumber) {
for (int i = 2; i < targetNumber - 1; ++i) {
if (targetNumber % i == 0) return false;
}
return true;
}소수는 항상 1과 자기 자신만을 약수로 가지기 때문에,
1과 자기 자신은 나누어 떨어지는 지에 대해 판단하지 않아도 됩니다.
먼저 targetNumber 는 소수인지 판별할 대상 자연수입니다. for 구문으로 진입하면 i 가 2부터 시작하여 대상 자연수 바로 직전 자연수에서 끝나는 것을 볼 수 있습니다.
하지만, 위와 같은 방식은 targetNumber 의 수가 커졌을 때는 시간 복잡도가 아무리 O(N) 이라고 하더라도 오래걸릴 수 밖에 없습니다.
그래서 다른 방식을 통하여 조금이라도 시간복잡도를 줄여 소수를 판별하는 방법을 다루어보려고 합니다.
제곱근을 사용하면 된다?!
이제 소수를 판별하기 위한 간단한 방법을 서술하려고 합니다.
위의 코멘트에서 언급 하였듯이, 제곱근을 이용하면 시간복잡도를 O(sqrt(N)) 까지 줄일 수 있을 것입니다.
예를 들어 N = 36 이라고 가정해 보겠습니다.
36 (1 과 자기 자신은 잠깐 고려하지 않겠습니다.)
2 * 18 = 36
3 * 12 = 36
4 * 9 = 36
9 * 4 = 36
12 * 3 = 36
18 * 2 = 36위 예시에서 볼 수 있듯이, 결국 약수 끼리의 곱셈은 서로서로 곱하게 되어있습니다. 이 점에서 미루어 보았을 때 해당 수의 제곱근 까지만 나누어 떨어지는지 확인해보면, 소수인지 아닌지 알 수 있다는 점을 알게됩니다.
대표적인 소수 13 에 대해 한 번 생각해보겠습니다.
13 의 제곱근은 3보다 크고 4보다 작습니다. 그렇다면 13이 소수인지 아닌지 판별하기 위해서는 2, 3으로 13이 나누어 떨어지는 지 확인해보면 됩니다.
코드로는 아래처럼 구현할 수 있겠습니다.
bool isPrimeNumber(int targetNumber) {
for (int i = 2; i <= sqrt(targetNumber); ++i) {
if (targetNumber % i == 0) return false;
}
return true;
}평소 제가 생각하고 있었던 소수 구하는 방법에 대해서도 사실 O(N) 의 시간 복잡도를 가지기 때문에 크게 문제가 있는 방법은 아니었다고 생각합니다.
혹시나 더 좋은 방법이 있으신 분들은 알려주시면 감사하겠습니다!!
