소수 구하기 (에라토스테네스의 체)

소수(Prime Number)약수로 1과 자기 자신만을 가지는 정수입니다. 정수론의 기본 정리에 의해 모든 자연수는 단 하나의 소수들의 곱으로 표현됩니다.

소수 구하는 알고리즘

1. 기본적인 접근

소수는 1과 N만을 약수로 가진다. 그럼 2부터 N-1까지의 수로는 나눠져서는 안된다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>
using namespace std;

int main(){
unsigned int num;
cout << "소수를 구할 수를 입력하세요 : ";
cin >> num;
bool isPrime = true;

// 2부터 N-1의 수로 나눠서 나눠지는 수가 있으면 반복문 종료
for (int i=2; i<num; i++) {
if (num % i == 0) {
isPrime = false;
break;
}
}

if(isPrime) {
cout << num << "은 소수입니다." << endl;
}
else {
cout << num << "은 소수가 아닙니다." << endl;
}

return 0;
}

연산 횟수 : N-2번

2. 에라토스테네스의 접근

주어진 자연수 N이 소수이기 위한 필요충분 조건은 N이 N의 제곱근보다 크지 않은 어떤 소수로도 나눠지지 않는다. 수가 수를 나누면 몫이 발생하게 되는데 몫과 나누는 수, 둘 중 하나는 반드시 N의 제곱근 이하이기 때문이다.

즉, 2부터 N의 제곱근 까지 나눠보면 됩니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>
#include <math.h>
using namespace std;

int main(){
unsigned int num;
cout << "소수를 구할 수를 입력하세요 : ";
cin >> num;
bool isPrime = true;

// 2부터 N의 제곱근까지의 수로 나눠서 나눠지는 수가 있으면 반복문 종료
for (int i=2; i<=sqrt(num); i++) {
if (num % i == 0) {
isPrime = false;
break;
}
}

if(isPrime) {
cout << num << "은 소수입니다." << endl;
}
else {
cout << num << "은 소수가 아닙니다." << endl;
}

return 0;
}

연산 횟수 : 루트(N-2) 번

3. 에라토스테네스의 체

에라토스테네스의 체는 매우 간단한 아이디어입니다. 위에서 모든 자연수는 소수들의 곱으로 표현이 된다고 했습니다. 제일 작은 소수 2부터 시작합니다. 2부터 N-1까지의 수 중에서 2의 배수를 모두 체로 거르고 남은 숫자들 중에서 3의 배수로 거르고를 반복해서 제곱근N 까지 나눠서 걸러지지 않고 남은 수들이 모두 소수가 됩니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>
#include <math.h>
using namespace std;

int main(){
unsigned int num;
cout << "소수를 구할 수를 입력하세요 : ";
cin >> num;

bool* prime = new bool[num+1];
memset(prime, 0, sizeof(bool) * (num + 1));

for (int i=2; i<=num; i++) {
if (prime[i] == false) {
for (int j=i*2; j<=num; j+=i) {
prime[j] = true;
}
}
}

for (int i=0; i<=num; i++) {
prime[i] = !prime[i];
}

if(prime[num]) {
cout << num << "은 소수입니다." << endl;
}
else {
cout << num << "은 소수가 아닙니다." << endl;
}

return 0;
}

주어진 수가 소수인지 아닌지 판별만 할 경우는 2번째 방법을 사용하는 것이 좋습니다.
그러나 다음 문제처럼 주어진 수 까지의 모든 소수를 구하기 위해서는 에라토스테네스의 체를 사용합니다.

다시 한번 간단하게 에라토스테네스의 체를 정리하며 마무리 하겠습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
prime[10000];

for (int i = 2; i < 10000; i++) {
if (prime[i] == false) {
for (int j = i*2; j < 10000; j += i) {
prime[j] = true;
}
}
}

for (int i = 0; i < 10000; i++) {
prime[i] = !prime[i];
}

참고 : 에라토스테네스의 체 - 위키백과