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

C#:ポラード・ロー素因数分解法

More than 1 year has passed since last update.

力ずくで素因数分解

まずは、与えられた数(long型)を力ずくで強引に素因数分解するプログラムを書いてみました。

C#のコード (Brute force版)

PrimeFactorBruteForce.cs
public class PrimeFactorBruteForce {
    private List<long> _factors = new List<long>();
    public IEnumerable<long> Enumerate(long num) {
        _factors.Clear();
        if (num == 1)
            return new long[] { 1 };
        var m = num;
        long n = 2;
        while (m > 1) {
            // m を nで割り続ける。その結果を返す。
            // かつ、割り切れたら、 _factorsにAdd
            while (m % n == 0) {
                _factors.Add(n);
                m = m / n;
            }
            n++;
        }
        return _factors;
    }
}

Enumerateを呼び出すと、素因数分解した結果である素因数が列挙できます。

しかし、このコード、大きな素数を与えた場合、めちゃくちゃ遅いです。
そこで、少し改良したのが次のコード

C#のコード (Brute force改良版)

PrimeFactorBruteForce2.cs
public class PrimeFactorBruteForce {
    private List<long> _factors = new List<long>();
    public IEnumerable<long> Enumerate(long num) {
        _factors.Clear();
        if (num == 1)
            return new long[] { 1 };
        var n = DivideWith(num, 2);
        n = DivideWith(n, 3);
        n = DivideWith(n, 5);
        long i = 0;
        while (n > 1) {
            int[] ps = { 7, 11, 13, 17, 19, 23, 29, 31 };
            foreach (var p in ps) {
                // 30m+2, 30m+3, 30m+4, 30m+5, 30m+6、30m+8... は割る必要はない。
                n = DivideWith(n, i + p);
                if (n == 1)
                    break;
            }
            i += 30;
        }
        return _factors;
    }

    // m を nで割り続ける。割り切れたら、 _factorsにAdd。
    private long DivideWith(long m, long n) {
        while (m % n == 0) {
            _factors.Add(n);
            m = m / n;
        }
        return m;
    }
}

すこし工夫して、単に、2,3,4,5,6,7...と順番に割り算をするよりは効率よく素因数分解するようにしています。

まず、31までの素数で割り、それ以降は、30m+7, 30m+11, 30m+13, 30m+17, 30m+19, 30m+23, 30m+29, 30m+31 の数で割っています。mは整数です。

30m+2, 30m+3, ..., 30m+8, 30m+9, 30m+10, 30m+12 などは、素数でないことが明らかなので対象から除外しています。そのため、素数でない数でも割ることにはなりますが、単純なコードよりもすこし効率良く素因数分解できます。

ただ、大きな素数が含まれる数に対しては、無意味な試し割りが何べんも行われるため、ほんのわずかに速度向上しただけでした。

ちなみにこのロジックは、ミラー・ラビン素数判定法による素数判定メソッドの中で示した力技のメソッドIsPrimeBruteforceと同じ考えで書いたコードです。

ポラード・ロー素因数分解法

もっと、速くする方法は無いのかと思って調べたら、ポラード・ロー素因数分解法というのがあることを知りました。

そこで、wikipediaのポラード・ロー素因数分解法 のページに書いてある通りに書いてみたのですが、どうも結果が正しくありません。

良く良く読むと、与える値は素数以外が大前提で、素数以外を与えても失敗する(素数でない因数を見つけてしまう)場合があると書いてあります。

ということで、そのあたりを改善したコードが次のコードです。
前の2つの方法に比べると、圧倒的な速さです。

PrimeFactor.cs
public class PrimeFactor {

    public IEnumerable<long> Enumerate(long n) {
        while (n > 1) {
            long factor = GetFactor(n);
            yield return factor;
            n = n / factor;
        }
    }

    private long GetFactor(long n, int seed = 1) {
        if (n % 2 == 0)
            return 2;
        if (IsPrime(n))
            return n;
        long x = 2;
        long y = 2;
        long d = 1;
        long count = 0;
        while (d == 1) {
            count++;
            x = f(x, n, seed);
            y = f(f(y, n, seed), n, seed);
            d = Gcd(Math.Abs(x - y), n);
        }
        if (d == n)
            // 見つからなかった、乱数発生のシードを変えて再挑戦。
            return GetFactor(n, seed+1);
        // 素数でない可能性もあるので、再度呼び出す
        return GetFactor(d);
    }

    private int[] seeds = new int[] { 3, 5, 7, 11, 13, 17 };
    private long f(long x, long n, int seed) {
        return (seeds[seed % 6] * x + seed) % n;
    }

    private static long Gcd(long a, long b) {
        if (a < b)
            return Gcd(b, a);  // 引数を入替えて自分を呼び出す
        if (b == 0)
            return a;
        long d = 0;
        do {
            d = a % b;
            a = b;
            b = d;
        } while (d != 0);
        return a;
    }

    // 効率は良くないが、これでも十分な速度がでたので、良しとする。
    private static bool IsPrime(long number) {
        long boundary = (long)Math.Floor(Math.Sqrt(number));

        if (number == 1)
            return false;
        if (number == 2)
            return true;

        for (long i = 2; i <= boundary; ++i) {
            if (number % i == 0)
                return false;
        }

        return true;
    }
}

IsPrimeメソッドを、ミラー・ラビン素数判定法による素数判定メソッドで示した最終版のメソッドに置き換えれば、もっと速くなると思います。

使い方はこんな感じ

var primeFactor = new PrimeFactor();
var line = Console.ReadLine();
var num = int.Parse(line);
var factors = primeFactor.Enumerate(num);
Console.Write(string.Join(" * ", factors));

実行例

以下、実行例です。

876402
2 * 3 * 3 * 181 * 269
1654620
2 * 2 * 3 * 5 * 11 * 23 * 109

この記事は、Gushwell's C# Programming Pageで公開したものを加筆・修正したものです。

Why not register and get more from Qiita?
  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
No 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
ユーザーは見つかりませんでした