Help us understand the problem. What is going on with this article?

分割統治法を利用した素因数分解のプログラムの最適化

More than 3 years have passed since last update.

こんにちは、Niaです。
今回は分割統治法を利用して、素因数分解を効率的に求めるアルゴリズムのお話です。

1. 素因数分解を行うプログラム

自然数$n$の素因数分解をする場合、$2$から$\sqrt n$(小数点以下は切り捨てます)まで試し割りをすることで求まります。

PrimeFactor1.cs
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 です。

PrimeFactor2.cs
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!
 

Why do not you register as a user and use Qiita more conveniently?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away