数字因式分解

Question

我正在尝试编写一个函数，该函数具有一个整数参数（我们称它为），结果 returns 一个由数字的所有质因数组成的向量，其中每个因数都显示为它在将数字分解为质因数时出现的次数。

#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 的数字。每次找到一个因子，只要它继续均分，就将 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;
}

数字因式分解

Factorization of numbers

c++

algorithm