寻找600851475143中最大的素数？ [英] Finding largest prime number out of 600851475143?

问题描述

我正在尝试从 http://projecteuler.net 解决问题3。但是，当我运行程序时，没有打印出来。
我做错了什么？
问题：600851475143的最大素数因素是什么？

I'm trying to solve problem 3 from http://projecteuler.net. However, when I run thing program nothing prints out. What am I doing wrong? Problem: What is the largest prime factor of the number 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);
    }
}

推荐答案

不只有你的 prime 检查函数总是返回 false ;即使它运行正常，你的主循环根本不会寻找输入数字的因子，而只是寻找小于或等于它的最大素数。在伪代码中，您的代码相当于：

Not only does your prime checking function always return false; even if it were functioning properly, your main loop does not seek the input number's factors at all, but rather just the largest prime smaller or equal to it. In pseudocode, your code is equivalent to:

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

但是你根本不需要素数检查功能。以下通过试验部门查找数字的所有因素：

But you don't need the prime checking function here at all. The following finds all factors of a number, by 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次迭代。

The testing for divisibility is done only up to the square root of the number. Each factor, as it is found, is divided out of the number being factorized, thus further reducing the run time. Factorization of the number in question runs instantly, taking just 1473 iterations.

通过构造，这样找到的所有因素都是保证是素数（这就是为什么不需要进行素数检查的原因）。在升序中枚举可能的除数至关重要，以使其发生 ¹ 。升序也是效率最高的，因为任何给定的数字更可能具有比较大的素数小的素因子。枚举素数而不是赔率，虽然没有必要，但如果你有一种有效的方法来获得这些素数，则可以更有效率来测试除以。

By construction all the factors thus found are guaranteed to be prime (that's why no prime checking is needed). It is crucial to enumerate the possible divisors in ascending order for this to happen¹. Ascending order is also the most efficient, because any given number is more likely to have smaller prime factor than larger one. Enumerating the primes instead of odds, though not necessary, will be more efficient if you have an efficient way of getting those primes, to test divide by.

增加以上内容以找到最大因素是微不足道的：只需实现追加为

It is trivial to augment the above to find the largest factor: just implement append as

append(fs,d):
    return d

---

¹
因为任何复合除数 d 原始数字被分解，当我们达到 d 时，我们已经将其素数除以原始数字，因此减少的数字将具有没有常见的素因子，即 d 即使它除以原始值，也不会除以减少的数量。

---

¹ because then for any composite divisor d of the original number being factorized, when we'll reach d, we will have already divided its prime factors out of the original number, and so the reduced number will have no common prime factors with it, i.e. d won't divide the reduced number even though it divides the original.

这篇关于寻找600851475143中最大的素数？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！