在600851475143中找到最大的质数？

Question

我正在尝试从http://projecteuler.net解决问题3 。但是，当我运行Thing程序时，没有任何输出。我究竟做错了什么？问题：600851475143的最大素数是多少？

public class project_3 

{

    public boolean prime(long x)   // if x is prime return true

    {

        boolean bool = false;

        for(long count=1L; count<x; count++)

        {

            if( x%count==0 )

            {

                bool = false;

                break;

            }

            else { bool = true; }

        }

        return bool;

    }

    public static void main(String[] args)

    {

        long ultprime = 0L;  // largest prime value

        project_3 object = new project_3();

        for(long x=1L; x <= 600851475143L; x++)

        {

            if( object.prime(x)==true )

            {

                ultprime = ((x>ultprime) ? x : ultprime);

            }

        }

        System.out.println(ultprime);

    }

}

Answer 1

您的prime检查功能不仅总是返回false；即使它正常运行，您的主循环也根本不会寻找输入数的因数，而只会寻找小于或等于它的最大素数。在伪代码中，您的代码等效于：foo(n):&nbsp; &nbsp; x := 0 ;&nbsp; &nbsp; foreach d from 1 to n step 1:&nbsp; &nbsp; &nbsp; &nbsp; if is_prime(d):&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; // always false&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; x := d&nbsp; &nbsp; return x&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;// always 0is_prime(d):&nbsp; &nbsp; not( d % 1 == 0 )&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; // always false但是您根本不需要这里的素数检查功能。以下内容按试算发现了所有的因素：factors(n):&nbsp; &nbsp; fs := []&nbsp; &nbsp; d&nbsp; := 2&nbsp; &nbsp; while ( d <= n/d ):&nbsp; &nbsp; &nbsp; &nbsp; if ( n % d == 0 ): { n := n/d ; fs := append(fs,d) }&nbsp; &nbsp; &nbsp; &nbsp; else:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; { d := d+1 }&nbsp; &nbsp; if ( n > 1 ): { fs := append(fs, n) }&nbsp; &nbsp; return fs除数测试仅进行到数字的平方根为止。如发现的那样，每个因子都从要分解的数量中除掉，从而进一步减少了运行时间。有关数字的因式分解可立即运行，仅需进行1473次迭代。通过构造，可以确保由此找到的所有因素都是主要因素（这就是不需要进行主要检查的原因）。至关重要的是要列举可能的除数以升序发生1。升序也是最有效的，因为任何给定的数字与更大的素数相比更可能具有较小的素数。如果您有一种有效的方法来求出质数，以进行除法运算，则枚举质数而不是赔率（虽然不是必需的）将更为有效。扩大上述内容以找到最大因素是微不足道的：只需实现append为append(fs,d):&nbsp; &nbsp; return d1， 因为对于d要分解的原始数的任何除数，当我们到达时d，我们已经将其素数除以原始数，因此缩减后的数将没有共同的素数，即d赢了即使减少了原数字，也不要将其减少。

Answer 2

两件事情：1）您从count1&nbsp;开始而不是2。所有整数都可以被1整除。2）您正在针对一个相当大的N运行O（n ^ 2）算法（或者至少在确定点＃1之后会运行）。运行时间将很长。

Answer 3

Euler项目的重点是，找到答案的最显而易见的方法将花费很长时间来计算，因此不值得运行。这样，您将学会寻找不太明显，更有效的方法。您的方法在技术上是否能够计算某个数的最大质数方面是正确的。您看不到任何输出的原因是您的算法无法快速解决问题。按照您设计的方式，大约需要4百万年才能完成。如果将600851475143数字替换为20，则可以很快完成。但是您有6000亿个数字，所以这不是那么简单。