[Algorithm] JAVA 소수판별 - 에라토스테네스의 체
ㅇ 소수란?
1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수
예를 들어 10보다 작은 소수는 2, 3, 5, 7이 있다.
ㅇ 소수 찾기
소수를 찾는 방법은 총 3가지가 있다.
1. N을 N보다 작은 자연수로 모두 나누기
2. N의 제곱근보다 작은 자연수로 모두 나누기
3. 에라토스테네스의 체 이용하기
ㅇ N보다 작은 자연수로 나누기
첫번째 방법은 매우 간단하면서 기초적인 방법이다.
N보다 작은 수로 모두 나누어 만약 나누어 떨어지는 것이 없다면 N은 소수일 것이다.
예를 들어보자.
만약 6이 주어졌을 때 1보다 크고 6보다 작은 수, 2, 3, 4, 5로 모두 나누어보자.
6 / 2 = 3
6 / 3 = 2
6 / 4 = 1 ... 2
6 / 5 = 1 ... 1
6은 2와 3으로 나누어 떨어지기 때문에 약수가 아니다.
[N보다 작은 자연수로 나누기]
public boolean isPrime(int n) {
if (n <= 1) return false; // 1보다 작으면 false 반환
for (int i = 2; i < n; i++) { // 2보다 크고 n보다 작은 수로 나눈다.
if (n % i == 0) return false; // 만약 나누어 떨어지는 것이 있다면 false 반환
}
return true; // 모두 나누고도 떨어지는 수가 없다면 true 반환
}n이 주어졌을 때 1보다 크고 n보다 작은 수로 모두 나눈 후 소수인지 아닌지 판별하는 알고리즘이다.
N까지의 과정을 모두 검사하기 때문에 시간 복잡도는 O(N)이다.
ㅇ N의 제곱근보다 작은 자연수로 나누기
이 방법은 첫 번째 방법에서 좀 더 발전된 방법으로 소수를 구할 때 굳이 N이하까지 모두 나누어 볼 필요가 없다는 방법이다. 즉, N의 제곱근(√) 까지만 나눈다는 뜻이다.
다시 6으로 예를 들어보자.
6 / 2 = 3
6 / 3 = 2
6 / 4 = 1 ... 2
6 / 5 = 1 ... 1
√4=2 < √6=2.xxx < √9 = 3
6을 나눌 때 2까지만 나누고 3이상은 나눠보지 않아도 3은 2로 나누어 떨어진다.
때문에 √N까지만 나누어도 된다는 뜻이다.
[N의 제곱근보다 작은 자연수로 나누기]
public boolean isPrime(int n) {
if (n <= 1) return false;
for (int i = 2; i <= Math.sqrt(n); i++) { // n의 제곱근까지 나누기
if (n % i == 0) return false;
}
return true;
}해당숫자의 제곱근까지 나누기 때문에 시간 복잡도는 O(√N)이다.
ㅇ 에라토스테네스의 체 이용하기
다음 방법은 소수판별에서 가장 효율적인 알고리즘이다.
1. 2부터 N까지의 수를 나열한다.
2. 2부터 가장 작은 수를 소수로 정하고 2의 배수를 모두 지운다.
3. 지우지 않은 수 중에서 가장 작은 수(3)를 소수로 정하고 그 배수(3의 배수)를 지운다.
이렇게 하나씩 지워나가다 보면 지워지지 않는 수들이 있는데 이들이 바로 소수이다.
위키백과에 해당 애니메이션이 있는데 이해하기 쉬워보여 가지고 왔다.
먼저 가장 작은 수인 2를 소수로 등록한 후, 2의 배수를 지운다.
지우지 않은 수 중 가장 작은 수인 3을 소수로 등록한 후, 3의 배수를 지운다.
이를 계속 반복하는 것이다.
[에라토스테네스의 체]
public boolean[] sieveOfEratosthenes(int n) {
//0부터 n까지의 수이기 때문에 n+1을 할당한다.
boolean[] prime = new boolean[n+1];
// 0과 1은 소수가 아니기 때문에 false를 저장한다.
prime[0] = false;
prime[1] = false;
// n의 제곱근까지 나눈다.
for(int i = 2; i <= Math.sqrt(n); i++) {
// 소수라면 뒤에 오는 코드를 스킵한다.
if(prime[i] == true) {
continue;
}
// 2부터 배수에 해당하는 수를 true로 변환한다.
for(int j = i * i; j < prime.length; j = j+i) {
prime[j] = true;
}
}
return prime;
}
에라토스테네스의 체 시간 복잡도는 O(Nlog(log N))이다.
N이하의 소수를 판별하는 것만 따지면 O(NlongN)이다.
하지만 여기서 이미 배수로 체크된 수는 나누지 않고 넘어간다. 즉, 최종적으로 정리하면 총 시간복잡도는 O(Nlog(log N))임을 알 수 있다.