查找600851475143中最大的素数？

我试图从http://projecteuler.net解决问题3。 但是，当我运行的东西程序没有打印出来。 我究竟做错了什么？ 问题：数字600851475143的最大素数是多less？

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 ， 即使它运作正常，你的主循环根本就不会查找input数字的因素，而只是最小的等于它的最小素数。 在伪代码中，您的代码等同于：

 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 

但是这里根本不需要素数检查function。 下面通过审判分区找出一个数字的所有因素：

 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 

对可分性的testing只能达到数字的平方根。 发现的每个因素都被分解出来，因此进一步缩短了运行时间。 有问题的数字因子分析立即运行，只需要1473次迭代。

通过构build，所有这些因素被保证是首要的（这就是为什么不需要检查）。 列举可能的因数是至关重要的。 升序也是最有效的 ，因为任何给定的数字更可能具有比较大的一个更小的素因子。 如果你有一个有效的方法来获得这些素数，然后除以，那么列举素数而不是不必要的，将会更有效率。

find最大的因素是增加以上的小事：只实现append as

 append(fs,d): return d 

---

¹ 因为那么对于原始数的任意复合因子d被分解了，当我们到达d ，我们已经将它的素数因子从原始数中分出来了，所以减less的数与它没有共同的素因子，即，即使将原来的数字分开， d也不会将减less的数字分开。

Answer 2

两件事情：

1）你从1开始count而不是2.所有整数都可以被1整除。

2）你正在运行一个O（n ^ 2）algorithm，对一个相当大的N（或者至less你会一旦你确定点＃1）。 运行时间会很长。

Answer 3

欧拉计划的重点在于寻找答案的最明显的方法将花费很长时间来计算，以至于不值得运行。 这样你就可以学习寻找不太明显，更有效的方法。

你的方法在技术上是否正确，无论它是否能够计算某个数字中最大的素数。 你没有看到任何打印出来的原因是你的algorithm不能快速解决问题。

你devise的方式，将需要约400万年完成。

如果用20来代替600851475143这个数字，那么它可以很快完成。 但是你有6000亿的数字，所以并不是那么简单。