C++ で素因数分解をするサンプルコードを紹介します。
素因数分解とは、ある整数を、素数の掛け算に分解する手法です。
素因数分解のためには、まず素数列が必要です。
以前の記事で掲載した素数ジェネレータクラス PrimeNumberGenerator を利用します。
がりテック
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, 
コメント