手順 |
方法 |
発見できない最小の数 |
0 |
2, 3, 5 で割る |
49 |
1 |
単純フェルマ法 |
119 |
2桁はこれで完了。25の素数をすべて憶えておくほうが実用的だと思いますが。 |
2 |
7, 11 で割る |
377=13*29, 403=13*31 |
377に注意すれば、400以下はこれで完了。 |
3 |
8倍フェルマ法(三角数法) |
533 |
4 |
13で割る |
799=17*47, 901=17*53, 1003=17*59 |
799, 901に注意すれば、3桁はこれで完了。単純フェルマ法のみの場合、943と989に注意して19まで、あるいは
23まで調べる必要がある。 |
5 |
17, 19, 23, 29, 31, 37で割る |
2881 |
6 |
24倍, 3倍フェルマ法 |
6437 |
7 |
16倍, 5倍フェルマ法 |
11521 |
4桁はこれで完了。単純フェルマ法のみの場合、9379に注意して73まで調べる必要がある。 |
2 及び 5 |
末尾の1桁を見ればわかる。 |
3 |
9=3^2で1桁に。 |
7 |
1001=7*11*13で3桁に。49=7^2。 |
11 |
99=11*9で2桁に。2桁の11の倍数は一見してわかる。 |
13 |
1001=7*11*13で3桁に。299=13*23で900以下に。39=13*3。 |
17 |
799=17*47で800以下に。51=17*3。(例えば119->11-9*5とする方法もある。) |
19 |
399=19*21で400以下に。19。(例えば133->13+3*2とする方法もある。) |
23 |
299=13*23で300以下に。69=23*3。(2001=29*23*3で2000以下に。) |
29 |
899=29*31で900以下に。29。(2001=29*23*3で2000以下に。) |
31 |
899=29*31で900以下に。31。(3999=43*31*3で4000以下に。) |
37 |
999=37*27で3桁に。111=37*3。 |
41 |
703=41*17。41。(2501=41*61) |
43 |
301=43*7。(3999=43*31*3で4000以下に。) |
47 |
799=17*47。47。 |
53 |
901=53*17。53。 |
59 |
1003=59*17。59。 |
61 |
305=61*5。61。(2501=41*61) |
67 |
201=67*3。 |
71 |
497=71*7。71。 |
73 |
10001=73*137。803=73*11。 |
79 |
1501=79*19。79。 |
83 |
249=83*3。 |
89 |
801=89*9。89。 |
97 |
97。 |