C言語で素因数分解アルゴリズムを教えて！
こういった悩みにお答えします．
本記事の信頼性
- リアルタイムシステムの研究歴12年．
- 東大教員の時に，英語でOS（Linuxカーネル）の授業．
- 2012年9月～2013年8月にアメリカのノースカロライナ大学チャペルヒル校（UNC）コンピュータサイエンス学部で客員研究員として勤務．C言語でリアルタイムLinuxの研究開発．
- プログラミング歴15年以上，習得している言語: C/C++，Python，Solidity/Vyper，Java，Ruby，Go，Rust，D，HTML/CSS/JS/PHP，MATLAB，Assembler (x64，ARM)．
- 東大教員の時に，C++言語で開発した「LLVMコンパイラの拡張」，C言語で開発した独自のリアルタイムOS「Mcube Kernel」をGitHubにオープンソースとして公開．
- 2020年1月～現在はアメリカのノースカロライナ州チャペルヒルにあるGuarantee Happiness LLCのCTOとしてECサイト開発やWeb/SNSマーケティングの業務．2022年6月～現在はアメリカのノースカロライナ州チャペルヒルにあるJapanese Tar Heel, Inc.のCEO兼CTO．
- 最近は自然言語処理AIとイーサリアムに関する有益な情報発信に従事．
- （AI全般を含む）自然言語処理AIの論文の日本語訳や，AIチャットボット（ChatGPT，Auto-GPT，Gemini（旧Bard）など）の記事を50本以上執筆．アメリカのサンフランシスコ（広義のシリコンバレー）の会社でプロンプトエンジニア・マネージャー・Quality Assurance（QA）の業務委託の経験あり．
- （スマートコントラクトのプログラミングを含む）イーサリアムや仮想通貨全般の記事を200本以上執筆．イギリスのロンドンの会社で仮想通貨の英語の記事を日本語に翻訳する業務委託の経験あり．
こういった私から学べます．
C言語を独学で習得することは難しいです．
私にC言語の無料相談をしたいあなたは，公式LINE「ChishiroのC言語」の友だち追加をお願い致します．
私のキャパシティもあり，一定数に達したら終了しますので，今すぐ追加しましょう！
独学が難しいあなたは，元東大教員がおすすめするC言語を学べるオンラインプログラミングスクール5社で自分に合うスクールを見つけましょう．後悔はさせません！
本記事は，素数の判定方法を理解していることを前提とします．
目次
素因数分解
素因数分解とは，ある正の整数（自然数）を素数の積の形で表すことです．
例えば，12を素因数分解した場合，\(12 = 2^2*3\)になります．
本記事では，C言語で以下の素因数分解アルゴリズムを紹介していきます．
- 試し割り法
- SPF法
試し割り法
試し割り法は，素因数分解する整数nを小さい順に割ってみて，割り切れるかどうかを調べるアルゴリズムです．
試し割り法は，シンプルでとても理解しやすい素因数分解アルゴリズムです．
試し割り法の計算量は，\(\mathcal{O}(\sqrt{n})\)になります．
計算量は指数関数的に増加しますが，現在の高速な素因数分解アルゴリズムでも同様に指数関数的に増加します．
なので，試し割り法は実用的なアルゴリズムと言えるでしょう．
試し割り法のコードは以下になります．
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 |
/* * Author: Hiroyuki Chishiro * License: 2-Clause BSD */ #include <stdio.h> #include <stdlib.h> #define PRIME_FACTOR_NUM 1000 int do_prime_factorization(unsigned long array[], unsigned long x) { int n = 0; unsigned long i; if (x == 0) { fprintf(stderr, "Error: x == 0\n"); exit(1); } else if (x == 1) { array[0] = 1; return 1; } while (x % 2 == 0) { array[n++] = 2; x /= 2; } i = 3; while (x > 1) { if (x % i == 0) { array[n++] = i; x /= i; } else { i += 2; } } return n; } int main(void) { unsigned long i, x, n; unsigned long array[PRIME_FACTOR_NUM]; do { printf("Please input a natural number: "); scanf("%lu", &x); } while (x == 0); n = do_prime_factorization(array, x); printf("%lu = ", x); for (i = 0; i < n; i++) { printf("%lu ", array[i]); if (i < n - 1) { printf("* "); } } printf("\n"); return 0; } |
実行結果は以下になります．
|
1 2 3 4 |
$ gcc trial_divison.c $ a.out Please input a natural number: 12 12 = 2 * 2 * 3 |
Smallest Prime Factor（SPF）法
Smallest Prime Factor（SPF）法は，エラトステネスの篩を利用して1からnまでの数に対する最小の素因数を前処理で求めてから素因数分解するアルゴリズムです．
前処理で求めたSPFを利用することで，素因数分解する本処理の計算量を減らすことができます．
具体的には，SPF法の前処理の計算量は\(\mathcal{O}(n \log\log n)\)，本処理の計算量は\(\mathcal{O}(\log n)\)になります．
計算量のlogの底は2なので，n = 4の場合，試し割り法とSPF法の本処理の計算量は等しくなります（\(\sqrt{4} = \log_2 4 = 2\)）．
\(\sqrt{n}\)と\(\log n\)はどちらも単調増加ですが，nが大きくなるほど\(\sqrt{n} - \log n\)は大きくなります．
しかし，SPF法の前処理の計算量\(\mathcal{O}(n \log\log n)\)が影響するので，1個の整数を素因数分解する場合，試し割り法はSPF法より速いです．
複数の整数を素因数分解する場合，SPF法は試し割り法より高速化できます．
なぜかというと前処理は1回，本処理は複数回あるからですね．
興味があるあなたは以下の記事を読みましょう！（C++のコードです．）
SPF法を利用するコードは以下になります．
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 |
/* * Author: Hiroyuki Chishiro * License: 2-Clause BSD */ #include <stdio.h> #define MAX_NUM 100001 #define PRIME_FACTOR_NUM 1000 unsigned long spf[MAX_NUM]; void calc_spf(void) { int i, j; spf[1] = 1; for (i = 2; i < MAX_NUM; i++) { spf[i] = i; } for (i = 4; i < MAX_NUM; i += 2) { spf[i] = 2; } for (i = 3; i * i < MAX_NUM; i++) { if (spf[i] == i) { for (j = i * i; j < MAX_NUM; j += i) { if (spf[j] == j) { spf[j] = i; } } } } } int do_prime_factorization(unsigned long array[], unsigned long x) { int n = 0; while (x != 1) { array[n++] = spf[x]; x = x / spf[x]; } return n; } int main(void) { unsigned long x; unsigned long array[PRIME_FACTOR_NUM]; int i, n; calc_spf(); do { printf("Please input a natural number: "); scanf("%lu", &x); } while (x == 0); printf("%lu = ", x); n = do_prime_factorization(array, x); for (i = 0; i < n; i++) { printf("%lu ", array[i]); if (i < n - 1) { printf("* "); } } printf("\n"); return 0; } |
実行結果は以下になります．
|
1 2 3 4 |
$ gcc smallest_prime_factor.c $ a.out Please input a natural number: 12 12 = 2 * 2 * 3 |
素因数分解とサマーウォーズ
素因数分解とアニメ映画「サマーウォーズ」は密接な関係があります．
サマーウォーズのネタになったRSA暗号が解けるかどうか検証している動画です．
面白いので，是非観ましょう！
まとめ
C言語で素因数分解アルゴリズムを紹介しました．
具体的には，試し割り法，SPF法を解説しました．
また，素因数分解とサマーウォーズの関係がわかりました．
素因数分解の高速化手法として，主に以下の方法があります．
興味があるあなたは，是非実装してみましょう！
素因数分解の高速化の現状について語る記事ですので，是非読みましょう！
C言語を独学で習得することは難しいです．
私にC言語の無料相談をしたいあなたは，公式LINE「ChishiroのC言語」の友だち追加をお願い致します．
私のキャパシティもあり，一定数に達したら終了しますので，今すぐ追加しましょう！
独学が難しいあなたは，元東大教員がおすすめするC言語を学べるオンラインプログラミングスクール5社で自分に合うスクールを見つけましょう．後悔はさせません！
