求大数阶乘​​的快速方法

Question

这是我的程序，但是对于像 100,000 这样的大数字，它的运行速度非常慢，有什么选项可以优化吗？

import java.math.BigInteger;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);

        int n = in.nextInt();

        BigInteger sum = BigInteger.valueOf(1);

        for (BigInteger i = BigInteger.valueOf(n);
             i.compareTo(BigInteger.ZERO) > 0;
             i = i.subtract(BigInteger.ONE)) {

            sum = sum.multiply(i);
        }

        System.out.println(sum);    
    }

}

Answer 1

这是我的第一个明显的实现：

public static void main(String[] args) {
        long start = System.currentTimeMillis();
        int n = 100000;
        BigInteger bigInteger = BigInteger.ONE;
        for (int i = 1; i < n; i++) {
            bigInteger = bigInteger.multiply(BigInteger.valueOf(i));
        }
        System.out.println(bigInteger);
        long end = System.currentTimeMillis();
        float total = end - start;
        System.out.println(total);
    }

100000 的阶乘是一个 456569 位的数字（所以我不能在这里打印它），我的解决方案大约需要 3.5 秒。

如果您无法做到这一点，则必须设计一个基于多线程的解决方案。例如，一个线程将前半部分相乘n，而另一个线程则对后半部分进行相同的操作。然后，将这两个数字相乘。