快速获取小于 100^100 的数字的质因数分解

Question

我想编写一个程序来比较大小为 100^100 的数字的质因数分解。我希望程序告诉我是否有一个 2，例如，在质因数分解中，但我不想知道有多少...而且我想比较两个数字的质因数分解.. . 有人可以帮忙吗？困难实际上是数字的大小...以及程序的效率...我希望比较两个数字最多只需要 10 秒...

我有这个；

import java.util.ArrayList;
import java.util.List;

public class PrimeFactorisation {
    public static List<Integer> primeFactors(int numbers) {
            int n = numbers;
            List<Integer> factors = new ArrayList<Integer>();
            for (int i = 2; i <= n / i; i++) {
                    while (n % i == 0) {
                            factors.add(i);
                            n /= i;
                    }
            }
            if (n > 1) {
                    factors.add(n);
            }
            return factors;
    }

    public static void main(String[] args) {
            System.out.println("Primefactors of 44");
            for (Integer integer : primeFactors(12345678901)) {
                    System.out.println(integer);
            }
    }
}

此代码适用于 Java，但我主要是在寻找高效的东西，所以我愿意更改语言...

Answer 1

这些都是巨大的整数。使用一个巨大的整数库，您可以通过处理低因子（但不是所有因子）很快将它们中的大部分降低到非常低的值 - 素数并不少见。

但是你不需要因数，你需要知道两个数是否有公因数。我相信有一个测试。它相当复杂，有点超出我的数学专业知识，但它是一个组件或随机素性测试。

Answer 2

一般来说，您将无法找到那么大的数的因数。但是，如果您只想知道两个数字是否具有除重数以外的相同因数，这很容易。使用欧几里得算法找出两个数的最大公因数。如果结果为 1，则这两个数互质并且没有相同的因数。否则，将最大公因数分解为素数；这应该比分解两个大数要容易得多，因为它可能会小得多。然后将每个大数除以每个公共质因数，直到不能均分为止；如果在除以所有公共质因数后，两个余数相同，则可以声明两个原始数具有相同的质因数但重数不同，否则您知道它们具有不共享的质因数.询问您是否需要了解更多。

这是一个相当奇怪的要求。你的用例是什么？也许还有其他方法可以解决根本问题。

快速获取小于 100^100 的数字的质因数分解

Getting the prime factorisation of a number rapidly less than 100^100

prime-factoring