找出 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

count

。所有整数都可以被 1 整除。

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

欧拉计划的全部要点是，寻找答案的最明显的方法将花费很长时间来计算，因此不值得运行。这样你就能学会寻找不那么明显、更有效的方法。

Answer 3

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

如果您将 600851475143 数字替换为 20，它将能够相当快地完成。但你有6000亿这个数字，所以事情没那么简单。

由于我们正在寻找最大的因子，因此我们需要从高处开始倒计时。 我们找到第一个，我们就退出了。 我们不需要所有的因素。 只有一个。 由于所有大于 4 的素数都是 6k+1，我们可以用它来加速搜索。 由于没有任何因子会大于 sqrt(600851475143)+1，因此我们从 6 开始倒数。为了确保我们使用的是正确的数字，我们需要使开始的数字在 6k+1 范围内，然后我们倒数到 7。因此 6k+1 个数字 mod 6 得到余数 1。7%6=1 13%6=1 等等。 开平方根 + 1 = 775147 %6 是 1！万岁，我们可以开始了。 现在我们倒数 6 并检查 6k+1，这将是 i 和 i-2，即 6k-1 一直到 7。然后我们检查 3 和 2 作为最后的结果。如果这一切都失败，则 n 是素数，我们返回它。

Answer 4

需要百分之几秒才能得到答案：

$ time python3 largest_prime_factor.py 
largest Prime Factor of 600,851,475,143 is 6,857

real    0m0.047s
user    0m0.043s
sys     0m0.005s