소수 문제에서 사용가능한 기법은 세가지 정도이다.
첫번째로 naive하게 2부터 n - 1까지 모든 수로 나누어버리는 방법이다.
// naive하게 소수판별
bool isPrime = true;
int num = 101;
for(int i = 2; i < num; ++i){
if(num % i == 0){
isPrime = false;
break;
}
}
if(isPrime) printf("%d is prime.\n", num);
else printf("%d is not prime.\n", num);
첫번째 방법을 좀 더 개선해보자. 수학적으로 어떤 한 수가 소수인지 판별하기 위해 그 수의 \(\sqrt n \)까지만 나누어주면 된다.
// naive하게 소수판별(개선)
bool isPrime = true;
int num = 101;
for(int i = 2; i <= (int)sqrt(num); ++i){
if(num % i == 0){
isPrime = false;
break;
}
}
if(isPrime) printf("%d is prime.\n", num);
else printf("%d is not prime.\n", num);
첫번째 방법도 소수를 판별하는 것에 나쁘지 않아 보인다.
그러나 어떤 구간 안에 있는 수 중에서 소수를 찾는 문제가 나오고, 그 구간 안에 너무 많은 숫자가 있거나 구간 안에 숫자들이 너무 크다면 이 방법은 가망이 없다.
왜냐하면 구간 안에 숫자 하나하나를 판별하는 건 시간 낭비가 심하기 때문이다.
그렇다면 한번에 연산으로 소수 판별이 가능한 방법이 있을까 ?
답은 "있다"이다. 바로 소수를 찾는 두번째 방법으로 소개할 '에라토스테네스의 체'라는 방법이 있다.
방법은 간단하다. 2부터 모든 소수들의 배수들을 배제하면 된다. 다시 말하면, 어떤 숫자 \(x\)가 배제되어있지 않다면 \(x\)는 소수일 것이다. 이게 어떻게 가능한지 보자.
여기 2부터 21까지 숫자가 있다.
| 2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
| 12 |
13 |
14 |
15 |
16 |
17 |
18 |
19 |
20 |
21 |
2부터 하나씩 숫자를 확인해보자. 2는 아직 배제된 적이 없다. 따라서 소수이기 때문에 2의 배수들을 모조리 배제해버리자. (배수들은 취소선이 긁히고, 소수는 파란색이 된다.)
| 2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
17 |
18 |
19 |
20 |
21 |
2에 대한 처리를 끝냈다. 이제 다음 숫자 3을 보자. 3 역시 아직 배제되지 않았다. 3을 소수로 취급하고 3의 배수들은 모조리 배제하자.
| 2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
17 |
18 |
19 |
20 |
21 |
3에 대한 처리를 끝냈다. 이어서 4를 봤더니 4는 이미 배제되어있다.
배제되었다는 뜻은 이 숫자가 어떤 숫자의 배수라는 것이기 때문에 소수일 수가 없다. 따라서 무시하고 지나간다.
다음으로 5는 배제되지 않았기 때문에, 소수이다. 5의 배수들을 처리해주자.
| 2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
17 |
18 |
19 |
20 |
21 |
위 표의 상황이 5까지 처리를 끝냈을 때의 상황이다. 계속 같은 처리를 진행해준다면 결과는
| 2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
17 |
18 |
19 |
20 |
21 |
이렇게 된다. 이 방법을 코딩만 해주면 우리는 에라토스테네스의 체를 구현할 수 있다.
// 에라토스테네스의 체
// 2부터 10000 사이에 있는 소수 확인
bool isPrime[10001]; // true면 소수 false면 소수가 아니다.
// 처음엔 모두 소수로 가정하기 위해
// 2~10000을 모두 true로 초기화, 1번 or 2번 중 취향에 맞게 사용
// 1번 memset 사용 (memset은 boolean 배열만 1로 초기화 가능)
memset(isPrime, 1, sizeof(isPrime));
// 2번 for문
for(int i = 2; i < 10001; ++i) isPrime[i] = true;
// standard
for(int current = 2; current < 10001; ++current){
// 이 숫자가 소수라면.
if(isPrime[current]){
// next는 current의 배수이기 때문에 loop를 돌 때마다 +1 아니라 +current를 해주어야한다.
for(int next = current * 2; next < 10001; next += current){
isPrime[next] = false; // 방금 찾은 소수의 배수들은 모두 소수가 아니다.
}
}
}
// Faster
for(int current = 2; current < 10001; ++current){
if(isPrime[current]){
// next * 2, next * 3 , ... next * (current - 1)은 이미 이전에 처리되었기 때문에
// 좀 더 빠른 속도를 원한다면 current의 제곱부터 true로 바꿔주어도 된다.
for(int next = current * current; next < 10001; next += current){
isPrime[next] = false;
}
}
}
isPrime의 size만 조절해주면 코더가 원하는 범위 안에 있는 소수들을 판별할 수 있다.
한가지 주의 사항은 4만 이상의 범위에서 faster 버전을 사용할 때 current * current가 int 범위를 초과하는 overflow가 날 수 있으니, 그 때는 long long 타입을 사용하자.
알고리즘이 나온 기념으로 시간복잡도를 얘기해보면 2~x까지 범위 안에 소수를 찾는데 걸리는 시간은 isPrime[]를 채우는 시간과 같다.
그럼 이중 for문을 사용해서 시간복잡도가 \(O(n^2)\) 아닌가요? 라고 물을 수 있는데 수학적으로 증명했을 땐 \(O(n log log n)\)이고, 평상시에 나는 그냥 isPrime[]을 한번 도는 시간 \(O(n)\)으로 생각하고 문제를 푼다.
마지막으로 소인수 분해 방법에 대해 알아보자.
소인수 분해 그거 대충 그냥 에라토스테네스의 체를 이용해서 찾은 소수들로 쭉 나누면 안되나요 ? 라고 물으면 가능하다라고 답할 수 있다. 다시 물어보자.
그럼 언제든 에라토스테네스의 체를 이용하면 소인수분해 문제를 풀 수 있네요? 라고 물으면 불가능하다라는 답변이 나온다.
왜일까?
여기 987,654,321를 소인수 분해하는 문제가 있다.
에라토스테네스의 체를 배웠으니 콧노래를 흥얼거리며 나는 bool isPrime[987654322]; 을 선언한다.
선언해보고 뭔가 이상함을 느낀다. 곧이어 이게 메모리를 버틸 수 있나? 라는 생각이 든다. 당연히 못버틴다.
혹시 모르니 백준에 제출해봤지만, 풀릴 리가 없다.
어떻게 할까 ?
방법은 이렇다. 꼭 소수로 나눌 필요가 없다.
어떤 수 x가 있으면 2로 나누어지지 않을 때까지 나누자.
나누어지지 않으면, 3으로 나누어지지 않을 때까지 나누자.
나누어지지 않으면, 4으로 나누어지지 않을 때까지 나누자.
나누어지지 않으면, 5으로 나누어지지 않을 때까지 나누자.
나누어지지 않으면, 6으로 나누어지지 않을 때까지 나누자.
...
나누어지는 수가 1이면 break.
아니 소인수 분해인데 소수로 안나누면 어떡합니까 ? ㅋㅋㅋㅋ 어이없네
어이없는 건 나다. 과정을 다시 생각해보자.
어떤 수 x가 있으면 2로 나누어지지 않을 때까지 나누자.
나누어지지 않으면, 3으로 나누어지지 않을 때까지 나누자.
나누어지지 않으면, 4으로 나누어지지 않을 때까지 나누자.
( 2로 이미 나누어지지 않을 때까지 나누었는데, 4로 나눠질까 ? 그럴 리가 없다. )
나누어지지 않으면, 5으로 나누어지지 않을 때까지 나누자.
나누어지지 않으면, 6으로 나누어지지 않을 때까지 나누자.
( 2랑 3으로 이미 나누어지지 않을 때까지 나누었는데, 6으로 나눠질까 ? 그럴 리가 없다. )
...
나누어지는 수가 1이면 break.
앞에서 먼저 등장한 소수들로 이미 다 나눴기 때문에, 뒤에서 나오는 합성수들로 백날 나눠봤자 아무 일도 안일어난다. 이게 핵심이다.
아니 그러면 소인수 분해할 수(n)가 소수면 n번 돌아야하는거잖아요 ㅡㅡ
어쩔 수 없다. 메모리가 못 버틴다. 이럴 땐 시간을 버리자.
// 987654321 소인수 분해
int num = 987654321;
int divisor = 2;
while (num != 1) {
// 나누어 떨어지지 않으면
if (num % divisor != 0) {
divisor++;
}
else{
cout << divisor << '\n';
num /= divisor;
}
}
코드를 적고 나니 개선점이 하나 떠올랐다.
2로 소인수 분해를 하고 나면 divisor가 짝수가 될 필요가 있을까 ? 없다. 2가 유일한 짝수인 소수이다.
그렇다면 3부터는 divisor에 1을 더하는 게 아니라 2를 더하여 홀수일 때만 확인해줘도 될까 ? 문제 없다. 개선하자.
// 987654321 소인수 분해
int num = 987654321;
int divisor = 2;
while (num != 1) {
if (num % divisor != 0) {
// divisor가 짝수면 +1, 홀수면 +2
divisor = divisor % 2 == 0 ? divisor + 1 : divisor + 2;
}
else{
cout << divisor << '\n';
num /= divisor;
}
}
개선이 끝났다. 라고 생각할 때쯤 한가지 생각이 더 든다.
위에서 소수 판별할 때 \(2\) ~ \(\sqrt n\)까지만 봐주면 된다는 점을 이용할 수 있을까 ? 있다.
어떤 정수 \(n\)가 있다고 가정해보자.
이 수를 \(2\)~\(\sqrt n\) 사이에 있는 정수로 나누어봤더니 그 어느 수와도 나누어 떨어지지 않았다.
이 때, \(\sqrt n\) 보다 큰 정수로 나누었을 때 \(n\)이 나누어 떨어질 확률은? 0이다.
왜? Why? 생각해보자.
만약 \(2\)~\(\sqrt n\) 사이에 어떤 정수 \(x\)로 \(n\)나누었더니 몫이 \(q\)이고 나머지가 0이다.
이 때 q의 범위는 ? 당연히 \(\sqrt n\) 이상이다. \(2\)~\(\sqrt n\)사이에 정수가 \(n\)을 나누어 떨어지게 할 수 있으면 그 몫은 자명하게도 \(\sqrt n\)보다 크다.
위 사실을 토대로 \(2\)~\(\sqrt n\) 사이에 어떤 정수로도 \(n\)을 나누어 떨어지게 할 수 없는데, \(\sqrt n\) ~ \(n\)사이에 있는 정수 중 \(n\)을 나누어 떨어지게 할 수 있는 수가 존재할까 ? 존재하지 않는다.
따라서 소인수 분해 코드를 다시 한번 개선하자.
// 987654321 소인수 분해
long long num = 987654321;
for(long long div = 2LL; div * div <= num; div = div % 2 == 0 ? div + 1LL : div + 2LL){
while(num % div == 0){
cout << div << '\n';
num /= div;
}
}
// for문이 끝나고 나온 num은 1이거나 소수이다.
if(num > 1){
cout << num << '\n';
}
지금까지 9단계 1~6번을 풀기 위한 초석이 될 방법들을 소개했다.
9단계 소수 문제들 뿐만 아니라 대부분의 소수 문제는 위 틀을 벗어나지 않기 때문에(최소 공배수, 최대 공약수 제외) 잘 습득해서 소수 문제를 풀 때마다 이 글이 생각나면 매우 기분이 좋을 것 같다.
오타나 이해가 안되는 점은 댓글로 부탁드린다.
