[알고리즘] 에라토스테네스의 체(Eratosthenes Sieve)

이번 글에서 써볼 내용은 수학에서도 나오는 개념인 

에라토스테네스의 체(Eratosthenes Sieve)입니다. 

 

정의 

• $2\le k\le \sqrt{n}$ 를 만족하는 $n$이하의 모든 $k$의 배수들을 제외시켜서 소수를 찾아내는 알고리즘 

 

동작 과정 

1. 2부터 $\sqrt{n}$까지 순회한다. 
   
   1. $\sqrt{n}\ast \sqrt{n}=n$이기 때문에 $\sqrt{n}$까지 오는 과정에서 $n$이하의 수들은 이미 모든 소수 판별이 끝나있다. 
2. 해당 수$(x)$가 제외된 수인지 아닌지 판단한다. 
   1. 제외되지 않은 수라면 $x^2$ 부터 $x$를 더하면서 더해진 수를 제외시킨다. 
      1. $x$이전의 수들과 $x$를 곱한 수들은 이미 처리가 끝났기 때문에 $x^2$부터 시작한다. 
   2. 소수가 아니라면 이어서 순회한다. 

 

구현

// 시간복잡도는 O(N log (log N))이다. 

#include <iostream>
#include <cmath>
using namespace std;

int era[101];

int main() {
	int sq = sqrt(100);
	era[0] = era[1] = 1;
	for (int i = 2; i <= sq; i++) {
		if (era[i]) continue;
		for (int j = i * i; j <= 100; j += i) era[j] = 1;
	}
}

 

 

 

이상으로 에라토스테네스의 체에 관한 내용을 마치겠습니다. 

읽어주셔서 감사합니다.