java - 从 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

但是你根本不需要这里的素数检查功能。下面通过 trial division 找到一个数的所有因数:

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 次迭代。

通过构造，所有由此找到的因子都保证是质数(这就是为什么不需要质数检查的原因)。要做到这一点，以升序枚举可能的除数是至关重要的¹。升序也是最最有效的，因为任何给定的数字都更有可能具有较小的质因数而不是较大的质因数。枚举素数而不是赔率，虽然不是必需的，但如果您有一种获取这些素数的有效方法来测试除以，将会更有效。

扩充上述内容以找到最大因子是微不足道的:只需将append实现为

append(fs,d):
    return d

---

¹因为对于被分解的原始数的任何复合除数 d，当我们达到 d 时，我们已经将其质因数除掉了原始数数，因此减少的数字将没有共同的质因数，即 d 不会除以减少的数字，即使它除以原始数字也是如此。