에라토스테네스의 체

개념

에라토스테네스의 체는 소수를 판별하는 알고리즘으로, 소수를 구하는 방법중 가장 효율적인 방법이라고 할 수 있다.

아래의 그림이 에라토스테네스의 체를 설명하고있다.

그림을보면, 2부터 120까지의 숫자중, 2부터 시작하여, 2를 제외하고 모든 2의배수를 체크한다. 

그리고 3으로 넘어가서 역시3을 제외한 모든 3의배수들을 체크한다. 다음으로 4인데, 4는이미 2의배수를 체크할때 체크되어서 4는 걸러지고 

모든 4의배수들이 체크된다. 이런 순서로 모든 수를 확인한 후 최종적으로 체크가 안 된 수들이 전부 소수다.

아래에 1~120까지의 수 중 소수를 판별하는 코드를 나타냈다. 소수의 시작은 2라서, 반복문의 시작을 i=2로했다. 

1은 별도로 1로 초기화 해준다.

코드

#include<iostream>
using namespace std;

//0~120까지의 수를 담을 배열
int arr[121];
int main()
{
	//1로체크된 수는 소수가 아닌 수임

	//1은 소수가 아니므로 체크
	arr[1] = 1;
	for (int i = 2; i <= 120; i++)
	{
		//4부터걸러지므로 j=i*i
		//j의 배수만큼 걸러지므로 증감값은 j+=i
		for (int j = i * i; j <= 120; j += i)
		{
			//걸러져있으면 다음 수로 넘어간다.
			if (arr[j] == 1)continue;
			//거른다. (소수가 아니다.)
			arr[j] = 1;
		}
	}
	//확인
	for (int i = 2; i <= 120; i++)
	{
		if (arr[i] != 1)
			cout << i << " ";
	}
	cout << endl;
}

결과

에라토스테네스의 체의 시간복잡도는 O(NloglogN)이다.(이유는 모르겠다.ㅠㅠ)