C++ | 素因数分解

C++ で素因数分解をするサンプルコードを紹介します。
素因数分解とは、ある整数を、素数の掛け算に分解する手法です。

素因数分解のためには、まず素数列が必要です。
以前の記事で掲載した素数ジェネレータクラス PrimeNumberGenerator を利用します。

アルゴリズムは、最も単純な試し割り法です。
小さい素数から順に、対象の整数を割り切れるかどうか試していきます。

#include <iostream>
#include <iterator>
#include <vector>

class PrimeNumberGenerator
{
  // 省略
};

std::vector<unsigned long> prime_factor(unsigned long n)
{
    std::vector<unsigned long> factors;
    PrimeNumberGenerator png;
    while (n > 1)
    {
        auto p = png();
        if (p * p > n)
        {
            factors.push_back(p);
            break;
        }
        while (true)
        {
            if (n % p != 0)
            {
                break;
            }
            factors.push_back(p);
            n /= p;
        }
    }

    return std::move(factors);
}

整数48に対して実行すると、2, 2, 2, 2, 3 と分解されます。

int main()
{
    auto factors = prime_factor(48);
    std::copy(factors.begin(), factors.end(), std::ostream_iterator<unsigned long>(std::cout, ", "));
    std::cout << std::endl;
    return 0;
}
$ g++ prime_factor.cc && ./a.out
2, 2, 2, 2, 3, 
  • URLをコピーしました!
  • URLをコピーしました!

コメント

コメントする

このサイトは reCAPTCHA と Google によって保護されていますプライバシーポリシー利用規約 申し込み。

The reCAPTCHA verification period has expired. Please reload the page.

目次