我试图在一个交互式网站上解决一个问题,在用我的一些示例尝试代码后,它似乎可以工作,但是,如果我将它加载到网站上,它说有一个错误的答案,这导致我认为在一种(或多种)情况下我的代码无法正确执行,但我似乎找不到这样的情况。
问题是:
对于每个给定的正整数,按升序返回其质因数。输入的第一行(一个自然数)是我们要检查多少个数字。在接下来的行中是大于 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;
}
}
最佳答案
我向你推荐使用算法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
关于c++ - 列出给定数字的质因数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/60887489/