■素数定理とエラトステネスのふるい(その2)

 2〜99の整数から,2の倍数,3の倍数,5の倍数,・・・をふるい落としてみましょう.

===================================

   0  1  2  3  4  5  6  7  8  9

0:       2  3  4  5  6  7  8  9

1:10 11 12 13 14 15 16 17 18 19

2:20 21 22 23 24 25 26 27 28 29

3:30 31 32 33 34 35 36 37 38 39

4:40 41 42 43 44 45 46 47 48 49

5:50 51 52 53 54 55 56 57 58 59

6:60 61 62 63 64 65 66 67 68 69

7:70 71 72 73 74 75 76 77 78 79

8:80 81 82 83 84 85 86 87 88 89

9:90 91 92 93 94 95 96 97 98 99

−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−

[1](2以外の)2の倍数をふるい落とす

   0  1  2  3  4  5  6  7  8  9

0:       2  3     5     7     9

1:   11    13    15    17    19

2:   21    23    25    27    29

3:   31    33    35    37    39

4:   41    43    45    47    49

5:   51    53    55    57    59

6:   61    63    65    67    69

7:   71    73    75    77    79

8:   81    83    85    87    89

9:   91    93    95    97    99

−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−

[2](3以外の)3の倍数をふるい落とす

   0  1  2  3  4  5  6  7  8  9

0:       2  3     5     7

1:   11    13          17    19

2:         23    25          29

3:   31          35    37

4:   41    43          47    49

5:         53    55          59

6:   61          65    67

7:   71    73     5    77    79

8:         83    85          89

9:   91          95    97

−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−

[3](5以外の)5の倍数をふるい落とす

   0  1  2  3  4  5  6  7  8  9

0:       2  3     5     7

1:   11    13          17    19

2:         23                29

3:   31                37

4:   41    43          47    49

5:         53                59

6:   61                67

7:   71    73          77    79

8:         83                89

9:   91                97

−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−

[4](7以外の)7の倍数をふるい落とす

   0  1  2  3  4  5  6  7  8  9

0:       2  3     5     7

1:   11    13          17    19

2:         23                29

3:   31                37

4:   41    43          47

5:         53                59

6:   61                67

7:   71    73                79

8:         83                89

9:                     97

−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−

[5](11以外の)11の倍数をふるい落とす

   0  1  2  3  4  5  6  7  8  9

0:       2  3     5     7

1:   11    13          17    19

2:         23                29

3:   31                37

4:   41    43          47

5:         53                59

6:   61                67

7:   71    73                79

8:         83                89

9:                     97

 ふるい落とされるものがない.11^2>99なので,これで99以下の素数はすべて求められたことになる.

===================================