素数判定

素数とは 「1 より大きい自然数で、正の約数が 1 と自分自身のみであるような数」です。

ある数 \(n\) が素数かどうかを判定するためには、単純に考えると \(O(n)\) の計算量になりますが、後述する通り実は \( ...