我试图通过我的代码找到任何数字的质因数。但是对于大数字，我的代码不会终止。为什么？

Question

我试图通过这段代码找到任何给定数字的素数。此代码适用于较小的数字，但对于较大的数字(如12345678(，程序不会终止。怎么了？？

using namespace std;
bool isPrime(int i)
{
for(int k=2;k<i;k++)
{
if(i%k==0)
{
return false;
}
}
if(i==1)
{
return false;
}
return true;
}
int main()
{
int n;
cout<<"Enter number"<<endl;
cin>>n;
for(int i=2;i<n;i++)
{
if(isPrime(i))
{
int x=n;
while(n%i==0)
{
cout<<i<<endl;
n=n/i;
}
n=x;
}
}
if(isPrime(n))
{
cout<<n<<endl;
cout<<1<<endl;
}
return 0;
}

Answer 1

这里有一个非常好的素数分解算法，只是考虑了一些细节。只需要检查i是否为素数，因为在您将找到的素数因子分解后，您一直在恢复n。

记住，如果你取N，然后把所有的2个因子都除以，那么没有偶数会是余数的除数。同样，如果你把这3个因子除以，那么没有一个可被3整除的数字会成为余数的除数。

或者换句话说：如果你从2开始向上计数并除以所有的除数，那么你找到的每个除数(在N的余数中(都必须是素数，因为为了让非素数成为除数，这个数字的素数因子也必须是除数，但所有较小的素数都已经被除以了。

使用这种逻辑，我已经删除了你的算法中一些多余的部分：

void printPrimes(int n)
{
for (int i = 2;i < n;i++)
{
//if (isPrime(i))
//{
//int x = n;
while (n % i == 0)
{
cout << i << endl;
n = n / i;
}
//n = x;
//}
}
//if (isPrime(n))
//{
cout << n << endl;
//}
}

如果我们稍微清理一下，并稍微改变一下外循环条件(这样最大的素数就不必在循环后打印(，我们最终会得到这样的结果：

void printPrimes(uint64_t n)
{
for (int i = 2;n > 1;i++)
{
while (n % i == 0)
{
cout << i << endl;
n = n / i;
}
}
}

编辑：我在这里的观点是指出，OP自己已经有了一个非常接近好的算法(就数字的大小而言，他发布的这个算法非常有效(，但正如评论中所指出的，它仍然可以做得更好。例如：

void printPrimes(uint64_t n)
{
while (n % 2 == 0)
{
std::cout << 2 << 'n';
n = n / 2;
}
for (uint64_t i = 3;i * i <= n;i += 2)
{
while (n % i == 0)
{
std::cout << i << 'n';
n = n / i;
}
}
if (n > 1)
std::cout << n << 'n';
}