素因数分解のアルゴリズム
素因数分解とは「ある自然数を素数の積の形に分解すること」です。
\(12 = 2^2 × 3\)\(1024 = 2^{10}\)
1つの自然数 n を \(O(\sqrt{n})\) で素因数分解する方法と ...
素数かどうかを判定するアルゴリズム
素数とは 「1 より大きい自然数で、正の約数が 1 と自分自身のみであるような数」です。
ある数 \(n\) が素数かどうかを判定するためには、単純に考えると \(O(n)\) の計算量になりますが、後述する通り実は \( ...