数因式分解

Question

我试图写一个有一个整数参数的函数(让我们称之为它)，它返回一个由数的所有素数因子组成的向量，其中每个因子显示的次数是它在将数分解成素数的过程中出现的次数的多少倍。

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

bool is_prime(int n)
{
    if (n <= 1)
        return false;
    for (int i = 2; i < sqrt(n); i++)
        if (n % i == 0)
            return false;
    return true;
}

std::vector<int> PrimeFactors(int n)
{
    std::vector<int> a, b, temp;
    for (int i = 1; i < n; i++)
        if (is_prime(i))
            temp.push_back(i);

    for (int i = 0; i < temp.size(); i++)
        for (int j = 0; j < temp.size(); j++)
            for (int k = 0; k < temp.size(); k++)
            {
                if (temp[i] * temp[j] == n)
                {
                    b.push_back(temp[i]);
                    b.push_back(temp[j]);
                    return b;
                }
                if (temp[i] * temp[j] * temp[k] == n)
                {
                    b.push_back(temp[i]);
                    b.push_back(temp[j]);
                    b.push_back(temp[k]);
                    return b;
                }
            }
}

int main()
{
    int n;
    std::cin >> n;
    std::cin.ignore(1000, '\n');
    for (int i : PrimeFactors(n))
        std::cout << i << " ";
    return 0;
}

将数字精确地存储在因式分解中的时间会使这有点困难。你能给出一个算法的想法吗？

Answer 1

使用%运算符查找均分n的数字。每次你发现一个因子，除以那个因子，只要它继续均分。

std::vector<int> PrimeFactors(int n) {
    std::vector<int> r;
    for (int i = 2; i * i <= n; i += 1 + (i > 2)) {
        while ((n % i) == 0) {
            r.push_back(i);
            n /= i;
        }
    }
    if (n != 1)
        r.push_back(n);
    return r;
}