项目Euler#3

Question

问题：

13195的质因数是5、7、13、29。

数字600851475143中最大的素因子是什么？

我发现这个很简单，但运行这个文件花了很长时间，已经运行了一段时间，我得到的最高数字是716151937。

这是我的代码，我只是要等待还是我的代码中有错误？

        //User made class
public class Three
{   
        public static boolean checkPrime(long p)
        {
            long i;
            boolean prime = false;
        for(i = 2;i<p/2;i++)
        {
            if(p%i==0)
            {
                prime = true;
                break;
            }
        }
    return prime;
    }   

}

    //Note: This is a separate file
public class ThreeMain
{
    public static void main(String[] args)
        {
            long comp = 600851475143L;
            boolean prime;
            long i;
            for(i=2;i<comp/2;i++)
            {
                if(comp%i==0)
                {
                    prime = Three.checkPrime(i);
                    if(prime==true)
                    {
                        System.out.println(i);
                    }
                }
            }
        }       
}

Answer 1

一旦你找到了你的数字的一个因子，你就可以把它除掉，使剩下的数字变小。

if (prime)
{
    System.out.println(i);

    // The factor may occur multiple times, so we need a loop.                
    do {
        comp /= i;
    } while (comp % i == 0);
}

这样做还保证了每当i划分comp时，i必须是素数，因为所有较小的素数都已被划分出来，因此您可以删除素数检查：

for (i = 2; i < comp/2; i++)
{
    if (comp % i == 0)
    {
        System.out.println(i);

        do {
            comp /= i;
        } while (comp % i == 0);
    }
}

最后，您只需要检查i，直到comp的平方根，因为任何大于平方根的因子都必须伴随一个小于平方根的因子。（即，如果i*j==comp，则i或j中的一个必须是

还有一些技巧可以应用，但对于这个问题来说，这应该足够了。

Answer 2

您可以简单地循环到sqrt（2）而不是n/2，这将节省大量时间。

Answer 3

你正朝着正确的方向前进，但是你已经远远超过了你需要去的地方，并且在这个过程中犯了一些错误。你现在检查的比你需要验证的质数高得多（尤其是质数

检查素数的函数实际上为复合函数返回true，而不是素数。您的代码：

    if ((p%i==0) {
        prime = true;
        break; }

应该是

    if ((p%i==0) {
        prime = false;
        break; }

在main方法中，实际上根本不需要布尔素数。从问题的上下文来看，我们可以假设将有两个以上的素数因子，这意味着我们需要将comp减少到一个更小且更易于管理的数字的最大素数因子是comp的立方根。因此，您的行（i=2；i

此外，您还可以：

    prime = Three.checkPrime(i);
    if(prime==true)

可减少至：

if (Three.checkPrime(i));

因为Three.checkPrime（）将返回并最终被评估为布尔值。