素数判定機

使い方

素数（prime number）とは、1と自分自身だけを約数に持つ、1より大きい自然数です。2、3、5、7、11、13のように約数が二つだけの数が素数であり、約数が三つ以上ある4、6、8、9は合成数に分類されます。

素数はすべての自然数を構成する「掛け算の原子」のような存在です。算術の基本定理により、1より大きいすべての自然数は素数の積として一意に分解されるからです。

この判定機は試し割り（trial division）に6k±1最適化を適用します。nが合成数なら約数の一つは必ず√n以下なので、2と3で先にふるい落とした後、5からi*i ≤ nの間、iとi+2のみを検査します。

核心となる条件：n < 2 → 素数ではない、そしてn % i === 0が一度でも真になれば合成数です。

たとえば97は√97 ≈ 9.85なので、2、3、5、7で割ってみるだけで十分です。97はいずれでも割り切れないため素数です。一方91は91 ÷ 7 = 13なので、91 = 7 × 13の合成数です。

素因数分解は小さい素数から順に割り、同じ因数は累乗でまとめて表記します。例：360 = 2³ × 3² × 5。

素数とは何ですか？

素数（prime number）とは、1と自分自身だけで割り切れる、1より大きい自然数です。たとえば2、3、5、7、11、13は素数です。1は素数ではなく、2は唯一の偶数の素数です。

1は素数ですか？

いいえ、1は素数ではありません。素数は1より大きい自然数のうち、1と自分自身、つまりちょうど二つの約数を持たなければなりませんが、1は約数が1だけです。1を素数から除くことで、素因数分解の一意性も成り立ちます。

素数判定の方法は何ですか？

最も基本的な方法は試し割り（trial division）です。ある数nが素数かどうかを確認するには、2から√nまでの数で割ってみて、一つでも割り切れれば素数ではありません。この計算機は6k±1最適化を適用し、5、7、11、13のように6の倍数の両隣の候補だけを検査するため、より高速です。

なぜ√nまで確認すればよいのですか？

nが合成数ならn = a × bと書けますが、aとbがどちらも√nより大きいことはありません。そうなるとa × bがnを超えて矛盾するからです。したがって約数の一つは必ず√n以下であり、その範囲まで検査すれば十分です。

素因数分解とは何ですか？

素因数分解とは、自然数を素数の積で表すことです。たとえば12 = 2² × 3、60 = 2² × 3 × 5です。算術の基本定理により、1より大きいすべての自然数は、順序を無視すればただ一つの素因数分解を持ちます。

なぜ2が唯一の偶数の素数なのですか？

2を除くすべての偶数は2を約数に持つため、1と自分自身のほかに2という約数がさらに生じて合成数になります。2だけが約数を1と2のみ持つので、偶数の中で唯一の素数です。

前の素数と次の素数はどう探しますか？

この計算機は入力値から上下に一つずつ移動しながら素数判定を繰り返し、最も近い前の素数と次の素数を見つけます。たとえば100を入力すると、前の素数97、次の素数101が表示されます。

どのくらい大きな数まで判定できますか？

この判定機は約10億（1,000,000,000）までの自然数を扱います。√nの範囲だけを検査する効率的なアルゴリズムなので、この程度の大きさなら即座に結果が出ます。それよりはるかに大きな数の判定には、ミラー・ラビンのような確率的素数判定法が使われます。

2026年検証済み数学公式