このツールでできること
これは素数に関する3つの機能を1つにまとめた計算ツールです。(1) n番目の素数 \(\text{Prime}[n] = p_n\) を求める、(2) 指定した整数が素数かどうかを判定し、素数であれば何番目の素数かを表示する、(3) 最初のN個の素数を一覧表示する、という3つの使い方ができます。最初の素数は 2, 3, 5, 7, 11, 13, 17, ... と続きます。素数とは、1より大きい整数のうち、正の約数が1と自分自身しかないもののことです。
使い方
まずモードを選びます。n番目の素数モードでは、1から数えた順番 \(n\)(例:100)を入力すると、\(\text{Prime}[100] = 541\) を返します。素数判定モードでは、任意の整数(例:97)を入力すると、その数が素数かどうかを判定し、素数であれば素数列の中での順番 \(n\) を表示します。最初のN個の素数を一覧表示モードでは、欲しい素数の個数を入力すると、カンマ区切りの一覧と、その中で最大の素数 \(\text{Prime}[N]\) を返します。
計算の仕組み
素数判定には試し割り法を使います。ある数 \(p\) が素数であるのは、次のように2から \(p\) の平方根までの間に約数が1つも存在しない場合です。
$$p \text{ prime} \iff p \ge 2 \;\wedge\; \nexists\, d \in [2,\sqrt{p}\,]: d \mid p$$まず2で割れるかを確認したあとは、\(d \times d \le p\) を満たす範囲で奇数の約数 \(d\) だけを調べればよく、高速かつ浮動小数点誤差も避けられます。n番目の素数は、2, 3, 4, ... と候補を順に走査し、素数を数え上げてその個数が \(n\) に達したところで求まります。素数 \(m\) の順番は \(\pi(m)\)、つまり \(m\) 以下の素数の個数に等しくなります。
具体例
97 を判定してみましょう。97は奇数なので、\(d = 3, 5, 7, 9\) で割れるかを試します(\(9^2 = 81 \le 97\) ですが、\(11^2 = 121 > 97\) のため、ここまでで十分です)。いずれでも割り切れないので、97は素数です。97以下の素数を数えると 2, 3, 5, ..., 97 で25個になるため、97は25番目の素数です(\(\text{primeIndex} = 25\))。
素数の参照表:最初の25個の素数と索引の目安
索引 \(n\) は素数を小さい順に並べたときの位置であり、\(p_n\) は \(n\) 番目の素数を表します。表には最初の25個の素数が並んでいます。
| n | pn | n | pn | n | pn | n | pn | n | pn |
|---|---|---|---|---|---|---|---|---|---|
| 1 | 2 | 6 | 13 | 11 | 31 | 16 | 53 | 21 | 73 |
| 2 | 3 | 7 | 17 | 12 | 37 | 17 | 59 | 22 | 79 |
| 3 | 5 | 8 | 19 | 13 | 41 | 18 | 61 | 23 | 83 |
| 4 | 7 | 9 | 23 | 14 | 43 | 19 | 67 | 24 | 89 |
| 5 | 11 | 10 | 29 | 15 | 47 | 20 | 71 | 25 | 97 |
索引の目安
| 記述 | 値 | 意味 |
|---|---|---|
| \(p_{100}\) | 541 | 100番目の素数は541です |
| \(p_{168}\) | 997 | 168番目の素数は997で、1000未満の最大の素数です |
| \(p_{1000}\) | 7919 | 1000番目の素数は7919です |
| \(\pi(10)\) | 4 | 10以下の素数:2、3、5、7 |
| \(\pi(100)\) | 25 | 100以下の素数は25個です(最後の素数は97) |
| \(\pi(1000)\) | 168 | 1000以下の素数は168個です |
| \(\pi(10000)\) | 1229 | 10,000以下の素数は1229個です |
2つの記法の関係に注意してください。\(p\) が素数のとき、\(\pi(p) = n\) は \(p = p_n\) であることと同値です。例えば、\(\pi(997) = 168\) かつ \(p_{168} = 997\) です。
素数の用語解説
- 素数:1より大きい整数で、その正の約数が1とそれ自身だけのもの(例:2、3、5、7、11)。
- 合成数:1より大きい整数で、1とそれ自身以外の約数を少なくとも1つもつもの(例:4、6、9、15)。
- 1は特別:数の1は素数でも合成数でもありません。正の約数はそれ自身の1つだけです。
- 2は唯一の偶数の素数:それ以外の偶数はすべて2で割り切れるため、合成数です。
- 素数の索引(位置)n:素数を小さい順に並べたときの順位。2の索引は1、3の索引は2、5の索引は3であり、以下同様です。したがって \(p_n\) は \(n\) 番目の素数を表します。
- 素数計数関数 \(\pi(x)\):\(x\) 以下の素数の個数。例えば \(\pi(10) = 4\)、\(\pi(100) = 25\) です。
- 試し割り法:\(p\) を2から \(\sqrt{p}\) までの各整数 \(d\) で割ってみる素数判定法。どれも \(p\) を割り切らなければ、\(p\) は素数です。どの因数の組も一方は必ず \(\sqrt{p}\) 以下になるため、\(\sqrt{p}\) までの確認で十分です。
- 互いに素:2つの整数の最大公約数が1であるとき、それらは互いに素(互いに素な関係)です。異なる2つの素数は常に互いに素ですが、互いに素な数が素数である必要はありません(8と15は互いに素です)。
- 双子素数:差が2である素数の組。例えば (3, 5)、(11, 13)、(17, 19)、(29, 31)、(41, 43) です。
よくある質問
1は素数ですか?いいえ。定義上、素数は1より大きい数でなければなりません。したがって1は素数でも合成数でもありません。
唯一の偶数の素数は?2だけが偶数の素数です。それ以外の偶数はすべて2で割り切れます。
100番目の素数は?\(\text{Prime}[100] = 541\) です。ほかの目安として、\(\text{Prime}[10] = 29\)、\(\text{Prime}[25] = 97\)、\(\text{Prime}[50] = 229\)、\(\text{Prime}[223] = 1409\) があります。