在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):

    x := 0 ;

    foreach d from 1 to n step 1:

        if is_prime(d):          // always false

            x := d

    return x                     // always 0

is_prime(d):

    not( d % 1 == 0 )            // always false

但是您根本不需要这里的素数检查功能。以下内容按试算发现了所有的因素：

factors(n):

    fs := []

    d  := 2

    while ( d <= n/d ):

        if ( n % d == 0 ): { n := n/d ; fs := append(fs,d) }

        else:              { d := d+1 }

    if ( n > 1 ): { fs := append(fs, n) }

    return fs

除数测试仅进行到数字的平方根为止。如发现的那样，每个因子都从要分解的数量中除掉，从而进一步减少了运行时间。有关数字的因式分解可立即运行，仅需进行1473次迭代。

通过构造，可以确保由此找到的所有因素都是主要因素（这就是不需要进行主要检查的原因）。至关重要的是要列举可能的除数以升序发生1。升序也是最有效的，因为任何给定的数字与更大的素数相比更可能具有较小的素数。如果您有一种有效的方法来求出质数，以进行除法运算，则枚举质数而不是赔率（虽然不是必需的）将更为有效。

扩大上述内容以找到最大因素是微不足道的：只需实现append为

append(fs,d):

    return d

1， 因为对于d要分解的原始数的任何除数，当我们到达时d，我们已经将其素数除以原始数，因此缩减后的数将没有共同的素数，即d赢了即使减少了原数字，也不要将其减少。

Answer 2

两件事情：

1）您从count1 开始而不是2。所有整数都可以被1整除。

2）您正在针对一个相当大的N运行O（n ^ 2）算法（或者至少在确定点＃1之后会运行）。运行时间将很长。

Answer 3

Euler项目的重点是，找到答案的最显而易见的方法将花费很长时间来计算，因此不值得运行。这样，您将学会寻找不太明显，更有效的方法。

您的方法在技术上是否能够计算某个数的最大质数方面是正确的。您看不到任何输出的原因是您的算法无法快速解决问题。

按照您设计的方式，大约需要4百万年才能完成。

如果将600851475143数字替换为20，则可以很快完成。但是您有6000亿个数字，所以这不是那么简单。