c++ - 列出给定数字的质因数

Question

我试图在一个交互式网站上解决一个问题，在用我的一些示例尝试代码后，它似乎可以工作，但是，如果我将它加载到网站上，它说有一个错误的答案，这导致我认为在一种(或多种)情况下我的代码无法正确执行，但我似乎找不到这样的情况。

问题是:

对于每个给定的正整数，按升序返回其质因数。输入的第一行(一个自然数)是我们要检查多少个数字。在接下来的行中是大于 2 的数字。对于每个数字(在一行中)返回该数字、一个分号及其升序排列的素因数。每个除数只能出现一次。

例子:

 2
 12
 1024

应该返回

12: 2 3
1024: 2

我的 C++ 代码:

#include <iostream>

using namespace std;

int prime_check(int n)
{
    for (int i = 2; i < n; i++)
    {
        if (n % i == 0)
        {
            return false;
        }
    }
    return true;
}

int main()
{
    int no_of_inputs;
    cin >> no_of_inputs;
    for (int i = 0; i < no_of_inputs; i++)
    {
        int val;
        cin >> val;
        cout << val<<": ";
        for (int i = 2; i < val; i++)
        {
            if (val% i == 0)
            {
                if (prime_check(i) == 1)
                {
                    cout << i<< " ";
                }
            }
        }
        cout << endl;
    }
}

Answer 1

我向你推荐使用算法Sieve of Eratosthenes因为您选择了所有质数并将质数除数分配给范围内的每个数字:

std::map<int, std::vector<int>> primeDiv;
bool noPrimes[MAXINTERGER] = {0};
void criba(){
    for(int i = 2; i <= MAXINTERGER; ++i)
        if(!noPrimes[i])
            for(int j = 2; i*j <= MAXINTERGER;j++){
                noPrimes[i*j] = true;
                primeDiv[i*j].push_back(i);
            }
}

最后在您的主函数中，val 的质因数是 primeDiv[val]，您可以迭代并打印这些值。小心呈现错误!

---

Sieve of Eratosthenes algorithm on action