| （解答） |
| |
| ある素数について、その数を除く倍数を消す作業を行うとき、その素数の倍数でそれより小さい数の倍数でもある数はすでに消されている。 |
| これにより、その素数について倍数を消す作業を行うべき最初の数は、その素数を2回かけたものになる。 |
| 1から1000までの数について、 |
| 31×31=961 |
| 32から36は素数ではないので、 |
| 37×37=1369 |
| 以上から、この作業を31まで行えば、1369未満で残っている整数は、1と素数。 |
| よって、求める答えは31 |
（答え） 31 |
| |
| （解説） |
| |
| “ある素数について、その数を除く倍数を消す作業を行うとき、その素数の倍数でそれより小さい数の倍数でもある数はすでに消されている。これにより、その素数について作業を行うべき最初の数は、この素数を2回かけたものになる。” |
| たとえば、ある素数を7とすると、7×7=49 |
| 49未満の7の倍数は、7，14，21，28，35，42 |
| このうち、14は2の倍数として消され、21は3の倍数として消され、28は2の倍数として消され、35は5の倍数として消され、42は2の倍数として消されている。 |
| つまり、2・3・5の倍数を消す作業によって、49未満の7を除く7の倍数は全て消されている。 |
| |
| （参考） |
| |
| 実際に問題のとおりの作業をすると、以下のようになります。 |
| ただし、この表では、2を除く偶数は明らかに素数ではないので奇数のみとしました。 |
| なお、3から31までの素数の文字の色とその数を除く倍数の背景の色が対応しています。 |
| これにより、31まで問題の作業を行えば、残った数は1と奇素数になります。 |
| |
| この方法は、エラトステネスのふるいといい、素数を発見する代表的な方法です。 |
| |
 |
| |
| ← 問題に戻る 次の問題 → |
 |
