[알고리즘] 소수구하기 - 에라토스테네스의 체 / C++

for문으로 구할 수 있지만, 시간복잡도면에서 효율성이 매우 떨어진다.

대안으로 에라토스테네스의 체를 이용하여 알고리즘을 짜면 훨씬더 빠른 속도로 소수를 구할 수 있다.

 

에라토스테네스의 체

출처: 위키백과

 

알고리즘

1	2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당한다.
2	2는 소수이므로 오른쪽에 2를 쓴다. (빨간색)
3	자기 자신을 제외한 2의 배수를 모두 지운다.
4	남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. (초록색)
5	자기 자신을 제외한 3의 배수를 모두 지운다.
6	남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. (파란색)
7	자기 자신을 제외한 5의 배수를 모두 지운다.
8	남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다. (노란색)
9	자기 자신을 제외한 7의 배수를 모두 지운다.
10	위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다.

그림의 경우,

이므로 11보다 작은 수의 배수들만 지워도 충분하다. 즉, 120보다 작거나 같은 수 가운데 2, 3, 5, 7의 배수를 지우고 남는 수는 모두 소수이다.

 

코드

#include <iostream>
#include<stdio.h>
#include<math.h>

using namespace std;

int main()
{
	int num = 10000; // 숫자 몇까지 검사하고 싶은지
	int arr[10000];

	for (int i = 2; i <= num; i++)
	{
		arr[i] = i;
        // 자기자신이 값인 아이들 : 소수
        // 값이 0인 아이들 : 소수 아님
	}

	for (int i = 2; i < sqrt(num); i++) //시간단축을 위해 제곱근까지 검사 
	{
		if (arr[i] == 0) continue; // 소수 아닌 애들은 건너뛰기 (= 소수일때만 아래 코드 실행)
		for (int j = 2 * i; j <= num; j += i)
		{
			arr[j] = 0; // 소수의 배수는 소수가 아니다.
		}
	}

	for (int i = 2; i <= num; i++)
	{
		if (arr[i] != 0) cout << arr[i] << " "; // 0이 아닌 애들이 소수다 (= 자기자신을 값으로 갖고있음)
	}

	return 0;
}

 

회고

볼때마다 찾게 되는 소수 구하기,, 이젠 외우자