에라토스테네스의 체(Sieve of Eratosthenes)

에라토스테네스의 체(Sieve of Eratosthenes)

고대 그리스의 수학자 에라토스테네스가 만들어 낸 비교적 작은 구간(10^8 이하)에서 소수를 빠르게 찾는 방법 입니다.

마치 체로 치듯이 수를 걸러낸다고 하여 '에라토스테네스의 체라고 부릅니다.

에라토스테네스의 체 소수 확인 과정

N개의 자연수를 모두 적습니다. 이 중 1을 제외한 2부터 진행을 합니다.

여기서 자기 자신을 제외한 자기자신의 배수를 제외시키면서 소수를 확인 합니다.

2의 경우 2를 소수로 지정하고, 2의 배수인 4, 6, 8, 10 등은 소수에서 제외합니다.

위와 같은 행위를 반복하여 소수를 찾습니다.

 

[출처] https://ko.wikipedia.org/wiki/에라토스테네스의_체

에라토스테네스의 체 예제

www.acmicpc.net/problem/1929

1929번: 소수 구하기

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

int sp, ep;
bool prime[1000002];

int main(int argc, char* argv[])
{
	scanf("%d %d", &sp, &ep);
	prime[0] = prime[1] = true;

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

	for (int i = sp; i <= ep; i++)
	{
		if (prime[i] == false)
			printf("%d\n", i);
	}
	return 0;
}