java - 使用 Java 查找 Long 数的素数

Question

public class prime
{
   public static void main(String[] args)
    {
     long thing = 600851475143L;
     for(long i = 300425737571L ; i == 0 ; i-- ){
     if (thing % i == 0)
     {
       long answer = i;
       System.out.println(answer);
       break;
     }
     }

    }

}

这是我目前拥有的代码，但是我已经在 DrJava 中运行了几分钟，但它没有返回任何结果。我猜有大约一百万种方法可以优化我的代码；谁能给我一些提示？

今天尝试解决一些编程问题，这给我带来了一些麻烦。

非常感谢：）

score 3 · Accepted Answer

为了计算不是非常大的值的素数，生成高达“事物”平方根的素数，然后一个一个地尝试它们会更有效。

可以完成质数生成：

或者使用 Eratosthenes 算法的 Sieve（参见http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes）
或使用试验划分算法（http://en.wikipedia.org/wiki/Trial_division）

score 3 · Accepted Answer

不过，您只需要向下迭代到 sqrt(thing)。

一般来说，从 2 开始迭代会更快，因为一半的数字将是 2 的因数（1/3 是 3 的因数等）。

你也只在第一个因素上打破，所以会错过任何其他因素

 long thing = 600851475143L;
 for(long i = 0; i < 300425737571L ; i++ ){
     if (i * i > thing) {
       break;
     }
     if (thing % i == 0) {
       long answer = i;
       System.out.println(answer);
       break;
     }
 }

正如 aioobe 所说，可以使用更复杂的方法

score 2 · Accepted Answer

不，它会立即终止，因为

i == 0

不会坚持第一次迭代。

你可能想写这样的东西：

public class Test {
    public static void main(String[] args) {
        long thing = 600851475143L;
        for (long i = 16857 /* 300425737571L */; i > 0; i--) {
            if (thing % i == 0) {
                long answer = i;

                // Print the largest prime factor, then break loop (and quit)
                System.out.println(answer);
                break;
            }
        }
    }
}

然而，这种简单的分解方法效率极低。由于600851475143is的因式分解，71 * 839 * 1471 * 6857您将不得不从 300425737571 迭代到 6857 并且每次都进行取模。有许多不那么复杂的方法可以瞬间解决多头分解。

java - 使用 Java 查找 Long 数的素数

3 回答 3

Related

Reference