(→같이 보기) |
|||
| (같은 사용자의 중간 판 5개는 보이지 않습니다) | |||
| 3번째 줄: | 3번째 줄: | ||
;에라토스테네스의 체 | ;에라토스테네스의 체 | ||
* [[소수(素數)]]를 찾아내는 방법 중 하나 | * [[소수(素數)]]를 찾아내는 방법 중 하나 | ||
* 에라토스테네스가 고안한 소수를 찾는 방법 | |||
* 마치 체로 수를 거르는 것과 같이 소수를 찾아내는 방법 | * 마치 체로 수를 거르는 것과 같이 소수를 찾아내는 방법 | ||
* 차례로 배열된 자연수에서 소수를 찾아내는 체계적인 방법 | * 차례로 배열된 자연수에서 소수를 찾아내는 체계적인 방법 | ||
| 27번째 줄: | 28번째 줄: | ||
* [[에라토스테네스]] | * [[에라토스테네스]] | ||
* [[함수 is_prime()]] | * [[함수 is_prime()]] | ||
* [[에라토스테네스의 체 구현 함수 eratosthenes()]] | |||
* [[에라토스테네스의 체 구현 클래스 Eratosthenes]] | |||
==참고== | ==참고== | ||
| 36번째 줄: | 39번째 줄: | ||
* {{네이버백과}} | * {{네이버백과}} | ||
[[분류: 에라토스테네스의 체]] | |||
[[분류: 소수]] | [[분류: 소수]] | ||
2023년 11월 30일 (목) 23:58 기준 최신판
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
12 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
12 345678910111213141516171819202122232425
12 345678910111213141516171819202122232425
12 345678910111213141516171819202122232425
3 같이 보기[ | ]
4 참고[ | ]
네이버백과 "에라토스테네스의 체"
로그인하시면 댓글을 쓸 수 있습니다.
{{ comment.name }}
{{ comment.created | snstime }}
-
{{comment.page_title}} ―{{comment.name}}