素数一覧ヘルプ

素数

素数とは，1 と自分自身以外の正の約数を持たない正の整数のことです．

素数の対義語は「合成数」です．合成数とは，1 と自分自身以外にも約数を持つ正の整数のことを指します．素数と合成数は，整数を分類する際の基本的な概念です．

1 は素数ではありません．1 と自分自身以外の正の約数を持たないという素数の定義を満たさないからです．

素数は無限に存在します．素数が有限個存在するという仮定が矛盾することにより平易に証明できます．

素数を覚えるのは大変なので，一覧表を見ましょう．

エラトステネスのふるい (Sieve of Eratosthenes) が有名です．このページの機能もこのアルゴリズムを利用して実装しています．時間計算量は O(n log log n) であることが知られており，素数を効率的に列挙できます．

素数と平方数の数を比較すると，素数の方が圧倒的に多いです．素数定理「ある正の整数 x に対して，x 以下の素数の個数は近似的に x / log(x) で与えられる」により，平方数 x² の数よりもたくさん存在することが分かります．

例えば，RSA 暗号などの公開鍵暗号システムにおいて，大きな素数 p と q を見つけ出すことが非常に困難であるという性質が用いられています．他にも，擬似乱数生成器は，素数の性質を利用して，ランダムな数列を生成します．