"에라토스테네스의 체"의 두 판 사이의 차이

2018년 7월 27일 (금) 16:59 판

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

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

@@ 8번째 줄: / 8번째 줄: @@
 * 자연수를 2에서 차례로 늘어놓고, 먼저 2의 배수를 지우고, 다음에 3의 배수를 지우고, 다음에는 5의 배수를 지우는 조작을 계속하여 소수 p에 도달하면, p²보다 작은 자연수로서 지워지지 않은 것이 모두 소수임
 * (1을 지움), 2를 제외한 모든 2의 배수을 지우고, 3을 제외한 모든 3의 배수를 지우고, (4는 지워졌으므로 넘김), 5를 제외한 모든 5의 배수를 지우고, … 이런 방식으로 계속해서 n을 제외한 모든 n의 배수를 지우면 남아 있는 수들이 소수가 됨
+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>
 ==같이 보기==