java - 找到一个非常大的数字

Question

所以，我正在尝试找到 600851475143 的最大质因数。我有一个简单的方法可以找到当前最大的质因数:

private static void findPrimeFactors(long num) {
        ArrayList<Long> list = new ArrayList<Long>();
        for (long i = 1; i <= num; i++) {
            int lol = 0;
            for (int a = 1; a < i; a++) {
                if (i % a == 0) {
                    lol++;
                }
            }
            if (lol < 2) {
                if (!list.isEmpty())
                    list.remove(list.size() - 1);
                list.add(i);
            }
        }
        System.out.println(list.get(list.size() - 1));
    }

请原谅我的糟糕编程，我仍在学习。我认为从列表中删除很多条目会减少计算时间，因此我删除了最后一个条目，除非它是最后一个。我可以用 100L 来完成，它输出以下内容:

97
Done in 1.0 milliseconds (0.001 seconds) (0.0625622 nano seconds)

还有 20,000:

19997
Done in 1774.0 milliseconds (1.774 seconds) (177.3702774 nano seconds)

正如您所看到的，在更大的数字中找到它需要相当长的时间。现在我应该在 600851475143 中找到我要查找的号码，所以我可以说这需要一段时间。我想知道他们是否有更快的计算方法？这是我的全部代码:

import java.util.ArrayList;


public class Main {

    public static void main(String[] args) {
        try {
        long num = 600851475143L;
        long time = System.currentTimeMillis();
        long timeNano = System.nanoTime();

        findPrimeFactors(20000);

        double finishTime = System.currentTimeMillis() - time;
        double finishTimeNano = System.nanoTime() - timeNano;
        System.out.println("Done in " + finishTime + " milliseconds (" + ((finishTime) / 1000) + " seconds)" + " (" + finishTimeNano / 10000000 + " nano seconds)");
        } catch (Exception e) {
            e.printStackTrace();
        }
    }

    private static void findPrimeFactors(long num) {
        ArrayList<Long> list = new ArrayList<Long>();
        for (long i = 1; i <= num; i++) {
            int lol = 0;
            for (int a = 1; a < i; a++) {
                if (i % a == 0) {
                    lol++;
                }
            }
            if (lol < 2) {
                if (!list.isEmpty())
                    list.remove(list.size() - 1);
                list.add(i);
            }
        }
        System.out.println(list.get(list.size() - 1));
    }
}

任何有关如何加快速度的提示都将受到赞赏!你们中的许多人可能知道我是在欧拉计划中这样做的。

Answer 1

你必须明白的第一件事是，你的任务本质上是“找到一个大数的一个素因数”。如果您知道怎么做，您可以将您的大数除以找到的因子并进行递归。

...但我很遗憾地告诉你，没有已知的算法可以在多项式时间内找到 laaaaarge 数的素因数。实际上，这在某种程度上是许多密码系统的基础(例如著名的 RSA)。

然而，现在600851475143这样大小的数字可以很快被分解。有很多算法可以做到这一点 - 但您必须学习一些数学才能理解它们。

就这个数字，我可以告诉你600851475143 = 71 * 839 * 1471 * 6857。