에라토스테네스의 체

1 개요

Sieve of Eratosthenes

에라토스테네스의 체

• 소수(素數)를 찾아내는 방법 중 하나
• 에라토스테네스가 고안한 소수를 찾는 방법
• 마치 체로 수를 거르는 것과 같이 소수를 찾아내는 방법
• 차례로 배열된 자연수에서 소수를 찾아내는 체계적인 방법
• BC 3세기경, 고대 그리스 수학자 에라토스테네스가 발견함
• 자연수를 2에서 차례로 늘어놓고, 먼저 2의 배수를 지우고, 다음에 3의 배수를 지우고, 다음에는 5의 배수를 지우는 조작을 계속하여 소수 p에 도달하면, p²보다 작은 자연수로서 지워지지 않은 것이 모두 소수임
• (1을 지움), 2를 제외한 모든 2의 배수을 지우고, 3을 제외한 모든 3의 배수를 지우고, (4는 지워졌으므로 넘김), 5를 제외한 모든 5의 배수를 지우고, … 이런 방식으로 계속해서 n을 제외한 모든 n의 배수를 지우면 남아 있는 수들이 소수가 됨

2 예시

• 1~25에서 소수를 찾아내는 예시

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

3 같이 보기

• 체(sieve)
• 소수
• 에라토스테네스
• 함수 is_prime()
• 에라토스테네스의 체 구현 함수 eratosthenes()
• 에라토스테네스의 체 구현 클래스 Eratosthenes

4 참고

• 위키백과 "에라토스테네스의 체"
• 위키낱말사전 "에라토스테네스의 체"
• 다음사전 "에라토스테네스의 체"
• 다음백과 "에라토스테네스의 체"
• 네이버사전 "에라토스테네스의 체"
• 네이버백과 "에라토스테네스의 체"