알고리즘을 공부하거나 코딩테스트를 준비하다보면 문제에서 요구하지 않더라도 풀이과정에서 소수판별 함수가 필요한 경우가 많다. 깊게 고민해보지 않았더니 계속 찾아보게 되어서 자세한 내용을 정리한다.
소수란 수학에서 1과 그수 자신 이외의 자연수로는 나눌 수 없는, 1보다 큰 자연수이다.
위의 명제를 따르자면 특정 수 N의 약수가 1과 N 2개로 떨어지면 소수라고 판별할 수 있다.
이걸 코드로 표현하면 다음과 같다.
// 소수판별 함수
// 1~N까지 반복하여 나누면서 나누어떨어지면 count를 증가시킨다.
public boolean isPrime(int N){
// 위의 명제에서 "1보다 큰 자연수"이므로 1은 소수가 아니다.
if( N == 1 ) return false;
int count = 0;
// i := 1 ~ N (i가 N의 약수인지 확인)
for(int i = 1; i <= N; i++){
if( N % i == 0 ){
count += 1;
}
}
return count == 2;
}위의 함수를 실행했을 때 숫자 N이 10억을 넘어가면?
모든 숫자를 반드시 순회하므로, 속도가 크게 떨어질 수 밖에 없다.
이 함수를 어떻게 개선할 수 있을까?
먼저 짝수를 생각해 볼 수 있다.
가장 작은 짝수 2는 약수가 1과 2로 두개이므로 소수라고 판단한다.
그러나 2보다 큰 짝수, 즉 4이상의 짝수는 반드시 약수를 2로 가진다.
4 → 1, 2, 4의 약수를 가진다.
6 → 1, 2, 3, 6의 약수를 가진다.
8 → 1, 2, 4, 8의 약수를 가진다.
따라서 2를 제외한 모든 짝수는 약수의 개수가 3이상이므로 소수가 아니다.
그렇다면 개선된 코드는 다음과 같다.
public boolean isPrime(int N){
// 1은 소수가 아니다.
if( N == 1 ) return false;
// 2는 소수다.
if( N == 2 ) return true;
// 2보다 큰 짝수는 소수가 아니다.
if( N % 2 == 0 ) return false;
int count = 0;
// i := 1 ~ N (i가 N의 약수인지 확인)
for(int i = 1; i <= N; i++){
if( N % 2 == 0 )
count += 1;
}
return count == 2;
}여기서 시간을 좀 더 줄이기 위해 생각할 수 있는 부분은 약수의 쌍에 대한 부분이다
예를 들어 숫자 100을 생각해보자. (100은 짝수지만 예를 들기 위해)
100의 약수는 1, 2, 4, 5, 10, 20, 25, 50, 100이다.
여기서 1과 100은 곱하면 N이 되므로 한쌍을 이룬다.
마찬가지로 2와 50은 한쌍이다.
4와 25 또한 한쌍이다.
5와 20은 한쌍이다.
10은 그 자신과 한쌍이다. (제곱)
그렇다면 10을 기준으로 두고 1,2,4,5를 왼쪽으로, 20,25,50,100을 오른쪽으로 놓고 보면
숫자 N (100) = a (1,2,4,5) * b (20,25,50,100)이라고 볼 수 있다. (단, a <= b)
여기서 약수 a가 있다면 쌍을 이루는 b도 반드시 존재한다는 전제가 깔린다.
그렇다면 우리는 a에서 1을 제외하고
2부터 10까지 반복하면서 a(왼쪽)가 1개라도 존재하는지 확인하면 되지 않을까?
숫자 10은 100(N)의 제곱근이면서 약수임을 생각한다면 코드는 다음과 같이 바뀔 수 있다.
public boolean isPrime(int N){
// 1은 소수가 아니다.
if( N == 1 ) return false;
// 2는 소수다.
if( N == 2 ) return true;
// 2보다 큰 짝수는 소수가 아니다.
if( N % 2 == 0 ) return false;
int count = 0;
// i := 2 ~ N의 제곱근 (i가 N의 약수인지 확인)
for(int i = 2; i <= Math.sqrt(N); i++){
if( N % i == 0 ){
count++;
}
}
return count == 0;
}위의 코드에서 이미 우리는 4이상의 짝수가 소수가 아니라고 위에서 판단하였으므로 홀수만 생각하면 된다.
그렇다면 코드는 다시 한번 아래와 같이 바뀐다.
public boolean isPrime(int N){
// 1은 소수가 아니다.
if( N == 1 ) return false;
// 2는 소수다.
else if( N == 2 ) return true;
// 2보다 큰 짝수는 소수가 아니다.
else if( N % 2 == 0 ) return false;
int count = 0;
// i := 3 ~ N의 제곱근 (i가 N의 약수인지 확인)
// 1을 제외한 홀수여야 하므로, 3으로 시작해서 2씩 증가한다. (3,5,7,9...)
for(int i = 3; i <= Math.sqrt(N); i += 2){
if( N % i == 0 ){
count++;
}
}
return count == 0;
}이때, N이 i로 나누어 떨어지면 → i가 N의 약수이므로,
count를 증가시키지 않고 반복문을 증가하며 false를 리턴한다.
public boolean isPrime(int N){
// 1은 소수가 아니다.
if( N == 1 ) return false;
// 2는 소수다.
else if( N == 2 ) return true;
// 2보다 큰 짝수는 소수가 아니다.
else if( N % 2 == 0 ) return false;
// i := 3 ~ N의 제곱근 (i가 N의 약수인지 확인)
// 1을 제외한 홀수여야 하므로, 3으로 시작해서 2씩 증가한다. (3,5,7,9...)
for(int i = 3; i <= Math.sqrt(N); i += 2){
// i가 N의 약수이면 count를 증가하지 않고 fasle 리턴
if( N % i == 0 ){
return false;
}
}
// 위의 반복문에서 종료되지 않았다면 약수가 없는 소수이므로 true 리턴
return true;
}