소수를 구하는 방법(1) 에라토스테네스의 체

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

에라토스테네스의 체(Sieve of Eratosthenes)는 1~N까지의 범위 내 소수를 모두 구하기 위한 방법이다

범위내의 자연수를 걸러내어 소수를 구하는 방법으로, 에라토스테네스의 체 라는 이름이 붙여졌다

1부터 40까지의 수 중 소수를 구해보며 에라토스테네스의 체 방법에 대해 알아보자

 

먼저 1부터 40까지의 숫자를 위와 같이 나열한다

 

소수란 1과 자기 자신만을 약수로 갖는 수를 말한다. 1은 소수에 해당하지 않으므로 지운다

모든 수가 1의 배수이므로 1의 배수를 걸러내는 과정은 생략한다

 

순서대로 하나하나 확인해 나가면 되는데, 자기 자신을 제외한 배수를 모두 지운다. 2를 제외한 2의 배수를 모두 지운다

 

그다음 숫자인 3을 확인한다. 3을 제외한 3의 배수를 모두 지운다

 

 

그 다음 숫자인 4는 2의 배수이므로 앞에서 이미 지워졌다

그다음 숫자인 5를 확인하고, 자기 자신을 제외한 5의 배수를 모두 지운다

 

 

6은 이미 지워졌으므로, 7을 확인한다. 7을 제외한 7의 배수가 더이상 남아있지 않으므로 다음 숫자로 넘어간다

 

 

다음 숫자인 11을 확인한다. 11일 제외한 11의 배수가 더이상 남아있지 않으므로 다음 숫자를 확인한다. 

 

 

남아있는 숫자에 이러한 과정을 반복하다보면 결국 소수만이 남는다