-1

给出答案需要很长时间，似乎只是在处理答案？我见过类似的问题，但请告诉我这段代码有什么问题？

#include<stdio.h>
main()
{
    int flag=0;
    unsigned long long int j,z,ino,i;
    scanf("%llu",&ino);
    for(i=2;i<=ino/2;i++)
    {
        flag=0; 
        if(ino%i==0)
        {
            for(j=2;j<=i/2;j++)
            {
                if(i%j==0)
                {
                    flag=1;
                }
            }

            if(flag==0)
            {
                z=i;
            }
        }
    }

printf("%llu",z);
}

这是问题所在：

13195 的质因数是 5、7、13 和 29。数字 600851475143 的最大质因数是多少？

4

1 回答 1

0

不是代码错误是不正确，而是效率低下是错误的。

让我们看看你的代码测试一个数字是否是素数：

            for(j=2;j<=i/2;j++)
            {
                if(i%j==0)
                {
                    flag=1;
                }
            }

如果您正在测试主要数字 7919（这是素数），您的循环将运行近 4,000 次。

但你的情况可能要强得多。如果你写：

        for(j=2;j<=sqrt(i);j++)
        {
            if(i%j==0)
            {
                flag=1;
            }
        }

那么你的素数测试仍然是正确的——但它只需要运行 88 次，这是一个巨大的改进。渐近地，您已经从用于测试素数的线性（n）算法更改为以根 n 时间运行的算法 - 您可以更快地测试素数，但至少在 Project Euler 中的前 50 个问题中您不必这样做.

我的这个项目欧拉问题的代码版本与您的代码版本相距不远，除了质数检查（而且它是在 Java 中），它运行时间为 0.023631 秒。

于 2014-04-07T21:05:11.057 回答