c++ - C ++：找到数字的最大素数的程序，我的代码有什么问题？

Question

这应该找到一个数字的最大素数..但它不起作用..答案应该是 6857，但它返回 688543..

int isPrime(unsigned long int n)
{
    for(unsigned long int i=2;i*i<(n);i++)
    {
        if(n%i==0)
        {
            return 0;
            break;
        }
    }
    return 1;
}

int main()
{
    unsigned long int num=600851475143;
    unsigned long int max=2, i=2;
    while(num!=1)
    {
        if(num%i==0 && isPrime(i))
        {
            max=i;
            num/=i;
            i--;
        }

        i++;
    }
    cout<<max;
    return 0;
}

提前致谢：）

Answer 1

unsigned long在您的系统上显然是 32 位的，所以num不是，600851475143而是. 是这个数字的最大素数，所以看起来你的算法至少可以正常工作。600851475143 mod 1<<323851020999688543

在您的编译器/系统组合上查找类型的最大范围，然后选择一个合适的。

Answer 2

除其他问题外，这将是大量问题：

for(unsigned long int i=2;i*i<(n);i++)

i*i对于大量数字将溢出unsigned long（在您正在编译的系统上似乎是 32 位）。

您可以通过切换它来修复它：

for (unsigned long int i = 2; i <= sqrt(n); ++i)

只要n没有溢出，sqrt(n)就会有效。unsigned long long但是，如果您要使用非常接近 32 位整数边界的数字，我仍然建议切换到 using 。