에라토스테네스의 체

에라토스테네스의 체는 대표적인 소수(prime) 판별 알고리즘이다.

--> 지금까지 for문 돌려서 약수 있으면 break 하는식으로 했다.

--> 더군다나 이 알고리즘은 중학교 수학에서 배울 수 있다고한다..

 

먼저 언급했던 for문을 돌려 1과 본인을 제외한 약수가 있다면, break 하는 방법은 시간 복잡도 O(N)을 가지고 있다.

에라토스테네스의 체를 사용하면, O(N^(1/2))의 시간복잡도를 가진다고 한다.

 

에라토스테네스의 체의 중점은 특정한 숫자의 제곱근까지의 약수의 여부를 검증하는 방식이다.

 

에라토스테네스의 체를 구현하는 방법은,

 

1. 이차원 배열을 생성하여 값을 초기화.

 

2. 2부터 시작해서 특정 숫자의 배수에 해당하는 숫자들을 모두 지움.

--> 지운다는 의미는 해당 배열의 값을 0으로 바꿔줌.

 

3. 3의배수, 4의배수, 5의 배수 .... 과정을 반복하여 지워줌.

 

4. 남아있는 숫자들을 출력.

 

코드는 이러하다.

 

// SieveofEratosthenes

#include <stdio.h>

int number = 100000;
int a[100001];

void SieveofEratosthenes()
{
	for (int i = 2; i <= number; i++)
	{
		a[i] = i;
	}

	for (int i = 2; i <= number; i++)
	{
		if (a[i] == 0) continue;
		for (int j = i + i; j <= number; j += i)
		{
			a[j] = 0;
		}
	}

	for (int i = 2; i <= number; i++)
	{
		if (a[i] != 0)
		{
			printf("%d ", a[i]);
		}
	}
}

int main(void)
{
	SieveofEratosthenes();
}