algorithm - 有没有办法用一些素数的乘法来分割一个数字

Question

我正在寻找一种算法来帮助我拆分数字N就像
N = (p ₁ ^a ) (p ₂ ^b ) .....*(p _n ^z )

在哪里

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

整数分解的算法有很多：试除法、Pollard 的 rho 算法、椭圆曲线、二次筛等。谷歌搜索其中一些主题会有所帮助。为了让你开始，这里是一个通过试除法分解的算法：

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

为了进一步阅读，我谦虚地在我的博客上推荐这篇文章。

Answer 3

如果我们不关心时间优化，这不是一个那么复杂的问题！以下是有效的简单代码。

#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;

}

希望能帮助到你！