0 
#include <stdio.h>
main()
{
    long n=600851475143;
    int i,j,flag;
    for(i=2;i<=n/2;i++)
    {
        flag=1;
        if(n%i==0)//finds factors backwards
        {
            for(j=2;j<=(n/i)/2;j++)//checks if factor is prime
            {
                if((n/i)%j==0)
                    flag=0;
            }
            if(flag==1)
            {
                printf("%d\n",n/i);//displays largest prime factor and exits
                exit(0);
            }
        }    
    }
}

上面的代码适用于n = 6008514751. 但是，它不适用于n = 600851475143，即使该数字仍在 a 的范围内long。
我该怎么做才能让它发挥作用？

4

5 回答 5

5

一个潜在的问题是iand jare int，并且可能会溢出很大n（假设int它比 更窄long，通常是这样）。

另一个问题是，对于 n=600,851,475,143，你的程序做了很多工作（最大的因素是 6857）。期望它需要很长时间才能完成并不是没有道理的。

于 2013-10-14T12:33:06.307 回答
2

用longs 代替ints。更好的是，使用uint64_t自 C99 以来已定义的用途（确认 Zaibis）。它是所有平台上的 64 位无符号整数类型。（您拥有的代码会在某些平台上溢出）。

现在我们需要让你的算法更快地工作：

您的素数测试效率低下；您不需要遍历所有偶数。只需遍历素数；最多等于您正在测试的数字的平方根（不是您当前所做的一半）。

你从哪里得到质数？好吧，递归调用你的函数。尽管实际上我很想将素数缓存到 65536。

于 2013-10-14T12:40:39.837 回答
1

在 32 位机器上，long范围从-2,147,483,648 to2,147,483,647和在 64 位机器上，范围从-9,223,372,036,854,775,808to 9,223,372,036,854,775,807（注意：这不是 C 标准强制要求的，并且可能因编译器而异）。
正如 OP 在评论中所说，他是 32 位的，600851475143超出范围，因为它不适合long.

于 2013-10-14T12:39:09.693 回答
1

来自 ISO/IEC 9899:TC3

5.2.4.2.1 整数类型的大小

[...]

它们的实现定义值的幅度（绝对值）应等于或大于所示的值，具有相同的符号。

[...]

— long int 类型对象的最小值

LONG_MIN -2147483647 // -(2^31 - 1)

— long int 类型对象的最大值

LONG_MAX +2147483647 // 2^31 - 1

编辑：

对不起，我忘了添加这应该告诉你的内容。

要点很长，甚至不需要能够保存您提到的值，因为标准规定它必须能够保存至少 4 个带符号的字节，因此您的机器可能只能保存值最多 2147483647 类型的变量long。

于 2013-10-14T12:34:25.977 回答
0

尝试更改n为long long int.. 并将 i,j 更改为 long

编辑：像这样定义n：

long long int n = 600851475143LL;

LL- 是强制 long long 类型的后缀...

于 2013-10-14T12:41:23.767 回答