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

에라토스테네스의 체란 고대 고리스의 수학자 에라토스테네스가 만들어 낸 소수를 찾는 방법. 이 방법은 마치 체로 치듯이

수를 걸러낸다고 하여 '에라토스테네스의 체'라고 부른다.따지고 보면 수열을 시각화한 것이라고 볼 수 있다.​

{방법}

1.일단 소수도 합성수도 아닌 유일한 자연수 1을 제거하자.

 

 

 

2. 2를 제외한 2의 배수를 제거한다.

 

 

 

3. 3을 제외한 3의 배수를 제거한다.

4. 4의 배수는 지울 필요 없다.(2의 배수에서 지워짐)그러면 2,3 다음으로 남아있는 가장 작은 소수,5의 배수를 제거한다.

5.마지막으로 7을 제외한 7의 배수까지 제거하면 결과는 이렇다.

 

  8의 배수는 지울필요없다.(2의 배수에서 이미 지워졌다.)9의 배수도 지울필요 없다.(3의 배수에서 이미 지워졌다.)10의 배수도 마찬가지다. 그리고 11이상의 소수 배수부터는 11 > 100루트이기에 역시 지울 필요가 없다.

  이런 식으로 남은 것들의 2배수, 3배수,...n배수를 지우다보면 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97이 남는다. 이것이 100 이하의 소수이다.

 

 

{마지막} 소스 코드

c언어

 

C++

 

 

 

 

[출처]

에라토스테네스의 체 - 나무위키 (namu.wiki)