こんにちは、Niaです。
今回は分割統治法を利用して、素因数分解を効率的に求めるアルゴリズムのお話です。
1. 素因数分解を行うプログラム
自然数$n$の素因数分解をする場合、$2$から$\sqrt n$（小数点以下は切り捨てます）まで試し割りをすることで求まります。
using System;
using System.Collections.Generic;
using System.Linq;
class Program {
static void Main( string[] args ) {
string s;
// 標準入力から読み取ります。
while( ( s = Console.ReadLine() ) != null ){
int n = int.Parse( s ); // 元の自然数
List<int> pfs = new List<int>(); // 素因数のリスト
int n1 = n;
int calcCount = 0; // 乗除回数
// もし、nが1であれば、1を素因数とします。
if( n == 1 )
pfs.Add( n );
else {
// 2から√nまで試し割りをします。
// ここでは i と Math.Sqrt( n ) を比較する代わりに i * i と n を比較します。
calcCount++; // forループの条件式判定時の乗算をカウントします。
for( int i = 2; i * i <= n; i++, calcCount++ ) { // forループの条件式判定時の乗算をカウントします。
// iで割り切れた回数分だけ、iを素因数のリストに追加します。
calcCount++; // while文の条件式判定時の除算(余剰)をカウントします。
while( n1 % i == 0 ) {
pfs.Add( i );
n1 /= i;
calcCount++; // 上の除算をカウントします。
}
}
// 2から√nまで割り切れない場合、その n1 の値が2以上であれば素数なので、素因数のリストに追加します。
if( n1 > 1 ) pfs.Add( n1 );
}
// 結果を出力します。
Console.WriteLine( "{0} = {1} ( 乗除回数 : {2} 回 )" ,
n,
string.Join( " × ",
// 素因数のリストを素因数ごとにまとめます。
pfs.GroupBy( pf => pf )
// "[素因数](^[その素因数の要素数])"の形式にします。
.Select( pf => string.Format( "{0}(^{1})", pf.Key, pf.Count() ) )
),
calcCount
);
}
}
}
◆ 実行結果
◇ 入力
2
12
100
121
1331
2048
9949
14400
19898
25401600
98903009◇ 出力
2 = 2(^1) ( 乗除回数 : 1 回 )
12 = 2(^2) × 3(^1) ( 乗除回数 : 8 回 )
100 = 2(^2) × 5(^2) ( 乗除回数 : 23 回 )
121 = 11(^2) ( 乗除回数 : 23 回 )
1331 = 11(^3) ( 乗除回数 : 74 回 )
2048 = 2(^11) ( 乗除回数 : 100 回 )
9949 = 9949(^1) ( 乗除回数 : 197 回 )
14400 = 2(^6) × 3(^2) × 5(^2) ( 乗除回数 : 249 回 )
19898 = 2(^1) × 9949(^1) ( 乗除回数 : 282 回 )
25401600 = 2(^8) × 3(^4) × 5(^2) × 7(^2) ( 乗除回数 : 10095 回 )
98903009 = 9941(^1) × 9949(^1) ( 乗除回数 : 19888 回 )
2. 分割統治法を利用して、素因数分解を行うプログラムを最適化する
例えば 100を素因数分解すると、「2が2個と5が2個」の積になりますが、
100=2^2\times5^2
「2が2個」と「25の素因数分解（ 5が2個の積 ）」に分けて考えることができます。
100=2^2\times25
\because 25 = 5^2
そこで私は思いつきました。『自然数の素因数分解は、ある素因数で試し割りを行い、その時の商に対して素因数分解を再帰的に行うことで求められる』のではないかと・・・。
先ほどのプログラムのforループの条件式にある n を n1 に変更し、n1 に対する素因数分解を求めるようにします。なお、n1 の初期値は n です。
using System;
using System.Collections.Generic;
using System.Linq;
class Program {
static void Main( string[] args ) {
string s;
// 標準入力から読み取ります。
while( ( s = Console.ReadLine() ) != null ){
int n = int.Parse( s ); // 元の自然数
List<int> pfs = new List<int>(); // 素因数のリスト
int n1 = n;
int calcCount = 0; // 乗除回数
// もし、nが1であれば、1を素因数とします。
if( n == 1 )
pfs.Add( n );
else {
// 2から√n1 まで試し割りをします。
// ここでは i と Math.Sqrt( n1 ) を比較する代わりに i * i と n1 を比較します。
calcCount++; // forループの条件式判定時の乗算をカウントします。
for( int i = 2; i * i <= n1; i++, calcCount++ ) { // forループの条件式判定時の乗算をカウントします。
// iで割り切れた回数分だけ、iを素因数のリストに追加します。
calcCount++; // while文の条件式判定時の除算(余剰)をカウントします。
while( n1 % i == 0 ) {
pfs.Add( i );
n1 /= i;
calcCount++; // 上の除算をカウントします。
}
// この時点で、n1 は 2～i で割り切れない値になります。
// 次の繰り返しで、n1 に対する素因数分解を行います。
}
// 2から√n1まで割り切れない場合、その n1 の値が2以上であれば素数なので、素因数のリストに追加します。
if( n1 > 1 ) pfs.Add( n1 );
}
// 結果を出力します。
Console.WriteLine( "{0} = {1} ( 乗除回数 : {2} 回 )" ,
n,
string.Join( " × ",
// 素因数のリストを素因数ごとにまとめます。
pfs.GroupBy( pf => pf )
// "[素因数](^[その素因数の要素数])"の形式にします。
.Select( pf => string.Format( "{0}(^{1})", pf.Key, pf.Count() ) )
),
calcCount
);
}
}
}
paiza.IOにもソースコードを載せてます。→ https://paiza.io/projects/zrZgPMkRRViIg7abxzLAwg
すると、例えば n = 100 と入力した時、forループの1回目の繰り返し（ i = 2 ）で、n1の値は25になるので、$2$ ～ $\sqrt{100}(=10)$であった i の範囲が、$2$ ～ $\sqrt{25}(=5)$ と小さくなります。25 に対して 6 ～ 10 の整数では割り切れないので、合理的です。
◆ 実行結果
◇ 入力
2
12
100
121
1331
2048
9949
14400
19898
25401600
98903009◇ 出力
2 = 2(^1) ( 乗除回数 : 1 回 )
12 = 2(^2) × 3(^1) ( 乗除回数 : 5 回 )
100 = 2(^2) × 5(^2) ( 乗除回数 : 13 回 )
121 = 11(^2) ( 乗除回数 : 23 回 )
1331 = 11(^3) ( 乗除回数 : 24 回 )
2048 = 2(^11) ( 乗除回数 : 14 回 )
9949 = 9949(^1) ( 乗除回数 : 197 回 )
14400 = 2(^6) × 3(^2) × 5(^2) ( 乗除回数 : 19 回 )
19898 = 2(^1) × 9949(^1) ( 乗除回数 : 198 回 )
25401600 = 2(^8) × 3(^4) × 5(^2) × 7(^2) ( 乗除回数 : 29 回 )
98903009 = 9941(^1) × 9949(^1) ( 乗除回数 : 19882 回 )
ここで、
- forループの条件式判定時の乗算
- while文の条件式判定時の除算(余剰)
- while文の中で ntmp を i で除算
を行った回数（乗除回数）を比較してみました。
◇ 乗除回数
| nの値 | 素因数 | PrimeFactor1.cs での乗除回数 c1 | PrimeFactor2.cs での乗除回数 c2 | c2 / c1 の比（※） |
|---|---|---|---|---|
| 2 | $2$ | 1 | 1 | 1 |
| 12 | $2^2 \times 3$ | 8 | 5 | 0.625 |
| 100 | $2^2 \times 5^2$ | 23 | 13 | 0.565 |
| 121 | $11^2$ | 23 | 23 | 1 |
| 1331 | $11^3$ | 74 | 24 | 0.324 |
| 2048 | $2^{11}$ | 100 | 14 | 0.14 |
| 9949 | $9949$ | 197 | 197 | 1 |
| 14400 | $2^6 \times 3^2 \times 5^2$ | 249 | 19 | 0.0763 |
| 19898 | $2 \times 9949$ | 282 | 198 | 0.7021 |
| 25401600 | $2^8 \times 3^4 \times 5^2 \times 7^2$ | 10095 | 29 | 0.0029 |
| 98903009 | $9941 \times 9949$ | 19888 | 19882 | 0.9997 |
※小数点以下4桁までを表示しています。
いくつかの自然数で実行してみたところ、n が素数でない場合、$2$から$\sqrt n$（小数点以下は切り捨てます）までの試し割りより少ない乗除回数で素因数分解を求めることができます。また、小さい素因数が多い程、乗除回数が少なくなります。
なお、n が素数もしくは素数の2乗の時は乗除回数が変わらず、また素因数の最小値が $\sqrt n$ に近い程、乗除回数はあまり減りませんでした。
以上のプログラムでは、2以上の自然数で試し割りをしていましたが、2以上の素数で試し割りをする時にも、その工夫による恩恵を得られると思います。
それでは、See you next time!