algorithm - いくつかの素数の乗算で数を分割する方法はありますか

Question

N =（p ₁ ^a）（p ₂ ^b） ..... *（p _n ^z）のように数値Nを分割するのに役立つアルゴリズムを探しています。

どこ

N is the given number
p is prime numbers smallest to greatest
a,b,..z are the power over the prime
* is the multiplication operation

Answer 1

それは因数分解と呼ばれます。グーグルへのキーワード：prime factorization algorithm。

問題は、これを本当に速く行うことがまだできないということです。これは、暗号化（RSAアルゴリズムなど）の非常に優れた基盤になります。

幸運を！

Answer 2

時間の最適化を気にしないのであれば、それほど複雑な問題ではありません。以下は、機能する簡単なコードです。

#include<iostream>
#include<vector>
#include<map>
#include<cmath>

using namespace std;

int get_primes(int max_number, vector<int> &primes)
{
    int *table = new int[max_number + 1];

    memset(table, -1, sizeof(int) * (max_number + 1));

    table[0] = table[1] = 0;

    primes.clear();

    for(int i = 2;i<=max_number ;i++)
    {
        if(table[i])
        {
            primes.push_back(i);
            for(int j = i * i;j<=max_number;j+=i)
            {
                table[j] = 0;
            }
        }
    }

    delete [] table;
    return primes.size();
}

int get_prime_factor(int number, map<int , int> &factors)
{
    vector<int> primes;
    get_primes(number,primes);

    factors.clear(); 
    int ret = 0;
    for(int i = 0;primes[i] <= number;)
    {
        if(number % primes[i] == 0)
        {
            ret ++;
            factors[primes[i]] ++;
            number /= primes[i];
        }
        else
            i++;
    } 
    return ret;
}

int main()
{
    cout<<"Please input a number:"<<endl;
    int number;

    cin>>number;

     map<int , int> factors;
     get_prime_factor(number,factors);


    for(map<int,int>::iterator itr= factors.begin();itr != factors.end();++itr)
    {
            cout<<"("<<itr->first<<"**"<<itr->second<<")";
    }

    cout<<endl;
    getchar();
    getchar();
    return 0;

}

それが役に立てば幸い！

Answer 3

整数を因数分解するためのアルゴリズムはたくさんあります。試行除算、ポラードのローアルゴリズム、楕円曲線、二次ふるい法などです。それらのトピックのいくつかをグーグルで検索すると役立ちます。はじめに、試行除算による因数分解のアルゴリズムは次のとおりです。

function td_factors(n)
    f = 2
    while f * f <= n
        if n % f == 0
            output f
            n /= f
        else
            f = f + 1
    output n

さらに読むために、私はブログのエッセイを控えめに勧めます。