使用 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 中运行了几分钟，但没有返回任何结果。我猜我的代码大约有一百万种可以优化的方法；有人能给我一些建议吗？

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

多谢 ：）

Answer 1

不过，您只需要迭代到 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 所说，可以使用更复杂的方法

Answer 2

为了计算不是很大的值的质因数，生成达到“事物”的平方根的质数，然后一一尝试会更有效。

素数生成可以通过以下方式完成：

• 使用埃拉托斯特尼筛算法（参见 http://en.wikipedia.org/wiki /Sieve_of_Eratosthenes）
• 或使用试除算法（http://en.wikipedia.org/wiki/Trial_division）

Answer 3

不，它会立即终止，因为

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;
            }
        }
    }
}

然而，这种简单的因式分解方法效率极低。由于 600851475143 的因式分解为 71 * 839 * 1471 * 6857，因此您必须从 300425737571 迭代到 6857，并每次都进行取模。有很多但并不复杂的方法可以立即解决长整数因式分解问题。