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

 

* 에라토스테네스의 체는 가장 대표적인 소수(Prime Number) 판별 알고리즘 이다. 이러한 소수들을 대량으로 빠르고 정확하게 구분하는 방법이다. 

   # 소수 : 양의 약수 두개만 가지는 자연수.

밀가루를 체로 거르기.

음식 만들 때나, 큰 덩어리와 그것보다 작은 덩어리를 분리 할 때 사용하는 체와 같은 원리라고 공부하였는데, 

크게 와닿을 것 같아, 정리하면서 한번더 생각하려한다.

 

* 에라토스테네스의 체 방식

- '자연수'를 체로 걸러내 소수만 추출해 내는 것.

1. 본문 첫 이미지처럼 1부터 60까지 수가 있다고 가정 해보자.

2. 모든 수의 약수인 1은 당연히 체에 걸러지게 된다.

3. 2는 약수가 1과 자기 자신뿐인 소수에 속하게 되는데 이상황에서 2를 제외하고 2의 배수를 전부 지워준다.

   (2가 아닌 2의 배수는 1과 2가 무조건 약수로 들어가며 자기 자신도 약수에 포함이기에 기본적으로 소수가 아니게된다.)

4. [3]번과 같은 방식으로 3,5,7,11... 증가되는 값을 가지고 자신의 숫자를 남기고 배수에 대해 모두 지워준다.

 결과 : 2, 3, 5,7,11,13,17,19,23,29,31,37,41,43,47,53   (본문 첫 이미지 참고)

 

위와 같은 방식으로 찾아내는 알고리즘이 에라토스테네스의 체 - 소수판별 방식이다.