素因数分解アルゴリズム: C, Python 例:
サラ・チェン
素因数分解とは何ですか?
数の素因数とは、それ自体が 素数1とそれ自身以外では割り切れない。
例： 10の素因数は2と5です。なぜなら、2 × 5 = 10だからです。
反復を使用して素因数を見つける
2からsqrt(n)までを繰り返し、割り切れるかどうかを確認します。nが現在の候補で割り切れる限り、割り算を実行して出力します。
例： 40より大きいすべての素数はnに適合する2+n+41なので、n = 0、1、2の場合、41、43、47が得られます。
数値の素因数を出力するにはどうすればよいですか?
- 2からsqrt(n)までの数値を繰り返します。
- 各候補に対してnの法則を調べます。余りがゼロであれば、その候補は素因数です。
- nを割り切るすべての素数を集めます。
- このルーチンはO(sqrt(n))の時間計算量で実行されます。
アルゴリズム：
Set a counter i to 2 While i <= sqrt(n): While n % i == 0: n = n / i print i i = i + 1 if n > 1: print n
ふるいアルゴリズム
篩法は、最大上限までのすべての数の最小の素因数を格納し、事前計算後に素因数分解のコストを大幅に削減します。
- 最大制限までのすべての整数の最小の素因数を記録します。
- その最小の素数を取り出して、因数集合に加えます。
- その数をその素数で割り、1になるまで繰り返します。
- 各クエリの実行時間は約O(log n)です。
例： 2と3以外の素数は、6n-1または6n+1の形に収まります。例えば、5 = 6(1)-1、19 = 6(3)+1です。
アルゴリズム： 定義する 配列 各数値の最小の素因数を格納し、インデックスを各要素の初期値として使用します。
Set array[1] to 1 Set i to 2 While i*i <= max_number: If array[i] == i: Set j to i*i While j <= max_number: If array[j] == j: array[j] = i j = j + i i = i + 1 while the_number != 1: print array[the_number] the_number = the_number / array[the_number]
関連記事
Python 反復法を使った素因数分解
以下 Python このコードは、反復試行除算法を用いて素因数を求めます。
import math def PrimeFactors(n): for i in range(2, int(math.sqrt(n)) + 1, 1): while n % i == 0: # find all the occurrences of a prime factor print((int)(i)) n = n // i if n != 1: # if the number was originally a prime print((int)(n)) n = (int)(input("Enter the number you want: ")) PrimeFactors(n)
出力：
Enter the number you want: 4 2 2
Python 再帰を使った素因数分解
その Python 以下のコードは、篩法を用いて与えられた数の素因数を求めます。
import math High = (int)(1e5 + 7) array = [0 for i in range(High)] # generate smallest prime factors def Sieve(): for i in range(1, High): array[i] = i for i in range(2, math.ceil(math.sqrt(High))): if array[i] == i: for j in range(i * i, High, i): if array[j] == j: array[j] = i def PrimeFactors(n): # divide until we reach 1 if n == 1: return print((int)(array[n])) PrimeFactors((int)(n / array[n])) Sieve() n = (int)(input("Enter the number you want: ")) PrimeFactors(n)
出力：
Enter the number you want: 4 2 2
反復を使用した C 素因数プログラム
同じ反復解法が C数値を入力し、2からsqrt(n)までの各候補について割り切れるかどうかをチェックし、素因数のすべての出現箇所を出力します。
#include <stdio.h> int main() { int n; printf("Enter the number you want: "); scanf("%d", &n); for (int i = 2; i * i <= n; i++) { while (n % i == 0) // find all the occurrences of a prime factor { printf("%d\n", i); n /= i; } } if (n != 1) // if the number was originally a prime { printf("%d", n); } return 0; }
出力：
Enter the number you want: 2 2
再帰を使用した C 素因数プログラム
再帰的なCバージョンは Python 1：最小の素因数の配列を作成し、nが1になるまでその素因数で割り続ける。
#include <stdio.h> int Max = 100007; int array[100007]; void Sieve() // smallest prime factors up to Max { for (int i = 1; i < Max; i++) array[i] = i; for (int i = 2; i * i <= Max; i++) { if (array[i] == i) { for (int j = i * i; j < Max; j += i) { if (array[j] == j) array[j] = i; } } } } void PrimeFactors(int n) { if (n == 1) // divide until we reach 1 return; printf("%d\n", array[n]); PrimeFactors(n / array[n]); } int main() { Sieve(); int n; printf("Enter the number you want: "); scanf("%d", &n); PrimeFactors(n); return 0; }
出力：
Enter the number you want: 2 2
素数に関する興味深い事実
- 2以外の偶数は、2つの素数の和として表すことができる（4 = 2 + 2、6 = 3 + 3、8 = 5 + 3）。
- 2と3以外に連続する素数は存在しない。なぜなら、2は唯一の偶数の素数だからである。
- 2と3を除くすべての素数は、6n + 1または6n − 1の形に当てはまります。ここでnは正の整数です。
- ある数の素因数の集合は一意である。
- 1は素数でも合成数でもない。
- 素因数分解は、割り算の判定、分数の簡略化、共通分母の探索に役立ちます。
- 素因数分解は、数値に基づく暗号コードの基礎も担っている。
