任意の数が素数かどうかを頭の中で判定できるようになりたいと思ったので,出題される数字が素数かどうかを判定するゲームを作成して練習することにしました.せっかくなので公開しました.
https://isprime.atsuhiro-me.net/
2から指定した値までの数から,ランダムに出題される数が素数かどうかを答えていき,連続で何回正答できるかを競うゲームです.
無料でご利用いただけます.ブラウザーで動作しますので気軽にご利用ください.
妥当性の検証
"show cheat sheet"ボタンを押すと,内部で保持している素数の一覧が表示されますので,ソフトウェアが正しく素数を判定できているがご確認いただけます.素数のリストは起動時にブラウザーで計算しております.
素数判定のコツ
素数を判定する決定的なアルゴリズムは,エラトステネスの篩,AKS素数判定法などたくさんありますが,いずれも高速に計算が可能な機械が必要です.頭の中で素数を判定するには,そのようなことはできないので,丸暗記するしかないでしょう.暗記量を減らす工夫をして,覚えます.
我々は10進法になれているので,10進法表記で数を扱うことを前提としたとき,10の位以上の部分でグループを作り,それぞれのグループに何個の素数が存在するかを記憶します.なお,1個のグループに含まれる素数の数は最小で0個,最大で4個であることはかんたんに証明できて,便利です.例えば20xの素数の数は0個だと覚えるだけで,201, 203, 207, 209はすべて素数ではないことが分かります.同様に,10xの素数は4個だと覚えるだけで,101, 103, 107, 109はすべて素数であると分かります.
参考のため,1000までのリストを以下に示します.
10の位以上 | 素数の数 | 素数 |
---|---|---|
0 | 4 | 2,3,5,7 |
1 | 4 | 11,13,17,19 |
2 | 2 | 23,29 |
3 | 2 | 31,37 |
4 | 3 | 41,43,47 |
5 | 2 | 53,59 |
6 | 2 | 61,67 |
7 | 3 | 71,73,79 |
8 | 2 | 83,89 |
9 | 1 | 97 |
10 | 4 | 101,103,107,109 |
11 | 1 | 113 |
12 | 1 | 127 |
13 | 3 | 131,137,139 |
14 | 1 | 149 |
15 | 2 | 151,157 |
16 | 2 | 163,167 |
17 | 2 | 173,179 |
18 | 1 | 181 |
19 | 4 | 191,193,197,199 |
20 | 0 | |
21 | 1 | 211 |
22 | 3 | 223,227,229 |
23 | 2 | 233,239 |
24 | 1 | 241 |
25 | 2 | 251, 257 |
26 | 2 | 263,269 |
27 | 2 | 271,277 |
28 | 2 | 281,283 |
29 | 1 | 293 |
30 | 1 | 307 |
31 | 3 | 311,313,317 |
32 | 0 | |
33 | 2 | 331,337 |
34 | 2 | 347,349 |
35 | 2 | 353,359 |
36 | 1 | 367 |
37 | 2 | 373,379 |
38 | 2 | 383,389 |
39 | 1 | 397 |
40 | 2 | 401,409 |
41 | 1 | 419 |
42 | 1 | 421 |
43 | 3 | 431,433,439 |
44 | 2 | 443,449 |
45 | 1 | 457 |
46 | 3 | 461,463,467 |
47 | 1 | 479 |
48 | 1 | 487 |
49 | 2 | 491,499 |
50 | 2 | 503,509 |
51 | 0 | |
52 | 2 | 521,523 |
53 | 0 | |
54 | 2 | 541, 547 |
55 | 1 | 557 |
56 | 2 | 563, 569 |
57 | 2 | 571,577 |
58 | 1 | 587 |
59 | 2 | 593,599 |
60 | 2 | 601,607 |
61 | 3 | 613,617,619 |
62 | 0 | |
63 | 1 | 631 |
64 | 3 | 641,643,647 |
65 | 2 | 653,659 |
66 | 1 | 661 |
67 | 2 | 673,677 |
68 | 1 | 683 |
69 | 1 | 691 |
70 | 2 | 701,709 |
71 | 1 | 719 |
72 | 1 | 727 |
73 | 2 | 733,739 |
74 | 1 | 743 |
75 | 2 | 751,757 |
76 | 2 | 761,769 |
77 | 1 | 773 |
78 | 1 | 787 |
79 | 1 | 797 |
80 | 1 | 809 |
81 | 1 | 811 |
82 | 4 | 821,823,827,829 |
83 | 1 | 839 |
84 | 0 | |
85 | 3 | 853,857, 859 |
86 | 1 | 863 |
87 | 1 | 877 |
88 | 3 | 881,883,887 |
89 | 0 | |
90 | 1 | 907 |
91 | 2 | 911,919 |
92 | 1 | 929 |
93 | 1 | 937 |
94 | 2 | 941,947 |
95 | 1 | 953 |
96 | 1 | 967 |
97 | 2 | 971,977 |
98 | 1 | 983 |
99 | 2 | 991,997 |