소수 구하는 문제는 코테 풀 때 종종 나오는 데 풀 때마다 까먹어서 정리해보려고 한다!
소수
소수는 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수이다.
자세히 뜯어서 살펴보면 조건이 2가지 이다.
조건1) 1보다 큰 자연수라는 것
조건2) 1과 자기 자신만을 약수로 가진다는 것
1보다 큰 자연수라는 것은 2부터 시작하는 자연수를 의미한다. 그래서 즉 0과 1은 제외하게 된다.
2, 3, 11, 17 과 같은 숫자들이 소수이고, 8, 12와 같이 1과 자기자신 외의 약수가 있는 숫자들은 소수가 아닌 합성수이다.
소수 판별 알고리즘
N보다 작은 자연수들로 나눠보기
가장 간단한 방법이다!
소수는 1과 자기 자신만을 약수로 가지는 수이기 때문에 자기 자신보다 작은 자연수들(1은 제외)로 나눠보고 나눠 떨어지지 않는다면 소수이고, 나눠 떨어지는 수가 있어서 1과 자기 자신 외의 약수가 있다면 소수가 아니게 된다.
boolean isPrime(int N){
// 소수 조건 1) 1보다 큰 자연수
if(N < 2) return false;
for(int i=2; i<N; i++){
if(N % i == 0)
return false;
}
return true;
}이 알고리즘은 N 이하의 모든 수를 검사하기 때문에 시간복잡도가 O(N)이 된다.
만약 N 이하의 소수들을 찾는 문제라면 N개의 수를 O(N) 만큼 반복하기 때문에 시간복잡도는 O(N^2)이 된다.
√N 이하의 자연수들로 나눠보기
N을 √N 이하의 자연수들로 나눠보는 방법이다.
왜 √N 이하의 자연수들만 나누면 되는지 수학적으로 알아보자.
먼저 간단한 예로 24를 살펴보자. 24의 약수는 1, 2, 3, 4, 6, 8, 12, 24 이다.
24는 24의 약수들의 곱으로 이루어져 있다. 2는 12와 곱했을 때 24가 되고, 4는 6과 곱했을 때 24가 된다. 24는 4와 6을 기준으로 양 쪽의 숫자들을 곱했을 때 24가 된다.
이 때 x를 기준으로 왼쪽의 수는 증가하고 오른쪽의 수는 감소하는 것을 볼 수 있다.
1 x 24 = 24
2 x 12 = 24
3 x 8 = 24
4 x 6 = 24
√24는 4.xx 이다. (√16 = 4 < √24 < √25 = 5)
24를 두 약수의 곱으로 나타냈을 때, 하나는 반드시 √24 이하의 수가 된다.
N = p x q 라고 해보자. N은 자연수이기 때문에 1 ≤ p, q ≤ N을 만족하게 된다.
24의 예시와 마찬가지로 p와 q 둘 중 하나는 반드시 √N 이하이다.
다시 말해 √N 보다 큰 약수들은 √N 이하의 약수들과 짝꿍이기 때문에 √N 이하인 약수들만 살펴봐도 가능하다.
즉, N이 1보다 큰 √N 이하의 자연수들로 나눠 떨어진다면 N은 소수가 아니게 된다.
boolean isPrime(int N){
// 소수 조건 1) 1보다 큰 자연수
if(N < 2) return false;
for(int i=2; i<=Math.sqrt(N); i++){
if(N % i == 0)
return false;
}
return true;
}위 코드에서 주의 할 점은 i는 Math.sqrt(N) 이하로 부등호에 =이 붙는다는 점이다!
이 알고리즘은 √N의 자연수들을 검사하기 때문에 시간복잡도가 O(√N)이 된다.
만약 N 이하의 소수들을 찾는 문제라면 N개의 수를 O(√N) 만큼 반복하기 때문에 시간복잡도는 O(N√N)이 된다.
에라토스테네스의 체
대망의 에라토스테네스의 체 ..!!!
이름에서 볼 수 있다시피 "체" 처럼 아닌 숫자들을 걸러내는 방법이다.
바로 위에 있는 √N을 이용하는 방법을 응용하는 방법으로 한 줄로 정의하면 다음과 같다.
k=2 부터 √N 이하까지 반복하여 자연수들 중 k를 제외한 k의 배수들을 제외시킨다
예를 들어 p는 2 이상의 자연수라고 했을 때, p의 배수라면 당연히 p를 약수로 가지기 때문에 p를 제외한 p의 배수는 소수가 될 수 없다.
따라서 배수들을 제외시키는 것이다.
또, 위에서 구했듯이 N가 소수인지 판별할 때 √N의 자연수들만 검사하면 되기 때문에 2부터 √N 이하까지 반복한다.
그림에서 보듯이 2부터 시작해서 2를 제외한 2의 배수들을 지워나간다. 2는 소수이기 때문에 오른쪽의 prime numbers에 넣는다.
그 다음 가능한 숫자는 3이다. 3을 제외한 3의 배수들을 지워나간다. 3은 소수이기 때문에 오른쪽의 prime numbers에 넣는다.
그 다음 가능한 숫자는 5가 된다. 마찬가지로 5를 제외한 5의 배수들을 지워나가고, 5를 prime numbers에 넣는다.
그림에서는 120 이하의 소수를 찾는 것인데, √120은 10.xx 이기 때문에 11보다 작은 수의 배수들까지만 지워줘도 충분하게 된다. 11보다 작은 수들의 배수들을 지웠다면 그 이상의 가능한 숫자들은 모두 소수이다.
boolean[] prime = new boolean[N + 1]; // 0 ~ N
void isPrime(int N) {
if(N < 2) {
return;
}
prime[0] = prime[1] = true;
for(int i = 2; i <= Math.sqrt(N); i++) {
// 이미 체크된 배열이면 다음 반복문으로 skip
if(prime[i]) continue;
// i를 제외한 i의 배수들 지우기
for(int j = i*i; j < prime.length; j += i) {
prime[j] = true;
}
}
}에라토스테네스의 체의 시간복잡도는 O(Nlog(logN))라고 한다.왜 인지는 추후 추가하기!
시간복잡도 비교
N 보다 작은 수√N 이하의 수에라토스테네스의 체
| O(N^2) | O(N√N) | O(Nlog(logN)) |
√N와 log(logN)를 비교하면, N=100 이라고 했을 때 √100 = 10, log(logN) = 0.3010 이다.
확실히 에라토스테네스의 체 방법이 시간복잡도가 작은 것을 알 수 있다.
소수 찾기 문제를 풀 때마다 에라토스테네스의 체가 생각이 안나서 Math.sqrt만 사용했었는데 앞으로는 에라토스테네스의 체를 활용해서 풀어야겠다!!