(새 문서: ==개요== ;Sieve of Eratosthenes ;에라토스테네스의 체 * 소수(素數)를 찾아내는 방법 중 하나 * 마치 체로 수를 거르는 것과 같이 소수를 찾아...) |
|||
| (같은 사용자의 중간 판 9개는 보이지 않습니다) | |||
| 3번째 줄: | 3번째 줄: | ||
;에라토스테네스의 체 | ;에라토스테네스의 체 | ||
* [[소수(素數)]]를 찾아내는 방법 중 하나 | * [[소수(素數)]]를 찾아내는 방법 중 하나 | ||
* 에라토스테네스가 고안한 소수를 찾는 방법 | |||
* 마치 체로 수를 거르는 것과 같이 소수를 찾아내는 방법 | * 마치 체로 수를 거르는 것과 같이 소수를 찾아내는 방법 | ||
* 차례로 배열된 자연수에서 소수를 찾아내는 체계적인 방법 | * 차례로 배열된 자연수에서 소수를 찾아내는 체계적인 방법 | ||
| 8번째 줄: | 9번째 줄: | ||
* 자연수를 2에서 차례로 늘어놓고, 먼저 2의 배수를 지우고, 다음에 3의 배수를 지우고, 다음에는 5의 배수를 지우는 조작을 계속하여 소수 p에 도달하면, p²보다 작은 자연수로서 지워지지 않은 것이 모두 소수임 | * 자연수를 2에서 차례로 늘어놓고, 먼저 2의 배수를 지우고, 다음에 3의 배수를 지우고, 다음에는 5의 배수를 지우는 조작을 계속하여 소수 p에 도달하면, p²보다 작은 자연수로서 지워지지 않은 것이 모두 소수임 | ||
* (1을 지움), 2를 제외한 모든 2의 배수을 지우고, 3을 제외한 모든 3의 배수를 지우고, (4는 지워졌으므로 넘김), 5를 제외한 모든 5의 배수를 지우고, … 이런 방식으로 계속해서 n을 제외한 모든 n의 배수를 지우면 남아 있는 수들이 소수가 됨 | * (1을 지움), 2를 제외한 모든 2의 배수을 지우고, 3을 제외한 모든 3의 배수를 지우고, (4는 지워졌으므로 넘김), 5를 제외한 모든 5의 배수를 지우고, … 이런 방식으로 계속해서 n을 제외한 모든 n의 배수를 지우면 남아 있는 수들이 소수가 됨 | ||
==예시== | |||
* 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 | |||
<s>1</s> 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 | |||
<s>1</s> 2 3 <s>4</s> 5 <s>6</s> 7 <s>8</s> 9 <s>10</s> 11 <s>12</s> 13 <s>14</s> 15 <s>16</s> 17 <s>18</s> 19 <s>20</s> 21 <s>22</s> 23 <s>24</s> 25 | |||
<s>1</s> 2 3 <s>4</s> 5 <s>6</s> 7 <s>8</s> <s>9</s> <s>10</s> 11 <s>12</s> 13 <s>14</s> <s>15</s> <s>16</s> 17 <s>18</s> 19 <s>20</s> <s>21</s> <s>22</s> 23 <s>24</s> 25 | |||
<s>1</s> 2 3 <s>4</s> 5 <s>6</s> 7 <s>8</s> <s>9</s> <s>10</s> 11 <s>12</s> 13 <s>14</s> <s>15</s> <s>16</s> 17 <s>18</s> 19 <s>20</s> <s>21</s> <s>22</s> 23 <s>24</s> <s>25</s> | |||
==같이 보기== | ==같이 보기== | ||
* [[체]] | * [[체(sieve)]] | ||
* [[소수]] | * [[소수]] | ||
* [[에라토스테네스]] | * [[에라토스테네스]] | ||
* [[함수 is_prime()]] | |||
* [[에라토스테네스의 체 구현 함수 eratosthenes()]] | |||
* [[에라토스테네스의 체 구현 클래스 Eratosthenes]] | |||
==참고== | ==참고== | ||
| 22번째 줄: | 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}}