'에라토스테네스의 체' 개념

에라토스테네스의 체

고대 그리스의 수학자 에라토스테네스가 만들어 낸 소수를 찾는 방법이다.
이 방법은 마치 체로 치듯이 수를 걸러낸다고 하여 '에라토스테네스의 체'라고 부른다.

 

임의의 자연수 n에 대해 그 이하의 소수를 찾는 가장 간단하고 빠른 방법이다.

 

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전

---

 

아래의 개념만 숙지하면 된다.

 

1. 소수란 '1과 자기 자신 외의 약수를 가지지 않는 1보다 큰 자연수'이다.

 

2. 소수의 배수는 소수가 아니다.

ex) 5는 소수이다. 5의 배수 10, 15, 20, 25... 는 소수가 아니다.

 

3. 자연수 n이하의 소수를 찾는다면  n½(루트 n) 보다 작은 수까지만 확인하면 된다.

ex) n = 122, n½(루트 n) 보다 작은 수 = 11    122는 2의 배수기 때문에 이미 앞에서 지워졌을 것이다. 따라서 11까지만 확인해도 된다.

 

4. 지워지지 않은 수는 소수이다.

 

---

예제

 

[알고리즘/에라토스테네스의 체] - 백준 1929 [소수 구하기]