3

我正在尝试从http://projecteuler.net解决问题 3 。但是，当我运行东西程序时，什么都没有打印出来。我究竟做错了什么？问题：数字 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);
    }
}
4

3 回答 3

6

您的检查功能不仅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赢了'不要除以减少的数字，即使它除以原始数字。

于 2013-03-08T11:26:58.150 回答
3

两件事情：

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

2）您正在针对相当大的 N 运行 O(n^2) 算法（或者至少在您确定点 #1 后您将是这样）。运行时间会很长。

于 2013-03-07T18:52:37.943 回答
3

欧拉计划的全部意义在于，寻找答案的最明显方法将花费很长时间来计算，以至于它们不值得运行。这样你就学会了寻找不那么明显、更有效的方法。

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

按照你设计的方式，大约需要 4,000,000 年才能完成。

如果您将 600851475143 号码替换为 20，它将能够很快完成。但是你有6000亿这个数字，所以没那么简单。

于 2013-09-18T01:01:54.500 回答