[Algorithm] 소수를 찾는 방법, 에라토스테네스의 체

 

에라토스테네스의 체 란?

소수(Prime number)를 찾는 알고리즘

대량의 소수를 빠르고 정확하게 구할 수 있는 방법

 

 

 

에라토스테네스의 체 원리

소수를 판별할 범위의 배열을 할당하고, 값을 지워나가는 방법

1. 배열을 생성하여 초기화

2. 2부터 시작하여, 특정 수의 배수를 모두 지운다. (자기 자신은 지우지 않는다)

3. 2부터 남아있는 모든 수는 소수이다.

 

 

 

에라토스테네스의 체 구현 (C++)

void Eratos(int n){

	/* 인덱스 0과 1은 사용하지 않음을 고려하여 배열을 할당해야 한다 */
	bool num[1000001];
    
	/* 배열 초기화 : 모두 소수라고 가정한 true 값을 준다 */
	for (int i = 2; i <= n; i++)
		num[i] = true;

	/* 소수 구하기 : n의 제곱근보다 작은 수만 검사해도 충분하다 */
	for (int i = 2; i * i <= n; i++)
	{
		if (num[i])
		{
			for (int j = i * i; j <= n; j += i)
				num[j] = false;
		}
	}
}

j 시작 값은 i * 2로 설정해도 되지만 i * k (k < i) 까지는 이미 검사되었으므로 i * i로 개선하였다.

 

 

 

에라토스테네스의 체 시간 복잡도

모든 수를 일일이 1과 자기자신으로만 나눠지는지 확인하는 알고리즘의 경우, 시간 복잡도가 O(N)이다.

모든 경우의 수를 다 돌면서 확인한다는 것이 몹시 비효율적이다.

사실 제곱근까지만 약수를 검증해도 되기 때문에 O(N^1/2)로 계산할 수 있다.

 

다만 이렇게 한 두개의 소수를 판별하는 것이 아닌 대량의 소수를 한꺼번에 판별하고자 하는 경우에

에라토스테네스의 체를 사용할 수 있다.

이 경우 시간 복잡도는 O(N log long N)이다.