如何打印到目前为止发现的最大素数？

Question

19世纪1月,建立了一项新的世界纪录:迄今为止发现的最大素数之一.这个数字达到了2 ^ 74207281 - 1,拥有超过2230万位数字.我在youtube上的numberphile频道上看到,他们将这个数字打印在一本由3部分组成的书中.现在我的问题是:你如何获得一个如此大的数字的字符串表示？显然这需要相当长的时间,但最有效的方法是什么？

我在Java中知道这样做的唯一方法是使用BigIntegers,这是最好的方法吗？用其他语言怎么样？

Answer 1

我在Java中知道这样做的唯一方法是使用BigIntegers,这是最好的方法吗？

简而言之

你的问题的答案是:是的.

详细地

我认为java和BigInteger是最好的解决方案.一个最小的例子可能如下所示:

public class Prime {

    public static void main(String[] args) {
        BigInteger number = new BigInteger("2")
                .pow(74207281)
                .subtract(new BigInteger("1"));
        System.out.println(number);
    }

}

更详细

也许最好让您的计算机以小组形式打印数字,而不是创建一个巨大的字符串 - 以获得更好的性能:

import java.io.File;
import java.io.FileOutputStream;
import java.math.BigInteger;
import java.util.LinkedList;

public class Prime {

    private static final BigInteger THOUSAND = new BigInteger("1000");

    public static void main(String[] args) throws Exception {
        BigInteger number = new BigInteger("2")
                .pow(74/*207281*/) // use 74207281 for the real number
                .subtract(new BigInteger("1"));

        System.out.println("calculation done, creating texts");

        int counter = 0;

        LinkedList<String> threes = new LinkedList<>();

        for (;;) {

            // divide by 1000 to get next 3 digits
            BigInteger[] divideAndRemainder = number.divideAndRemainder(THOUSAND);
            number = divideAndRemainder[0];
            BigInteger lastThreeDigits = divideAndRemainder[1];

            // format digits, with leading zeros
            String text = String.format("%03d", lastThreeDigits);

            // add them to the list
            threes.addFirst(text);

            // stop, if we reached the end
            if (number.signum() == 0) {
                break;
            }

            // print progress
            if (counter++ > 999) {
                System.out.print(".");
                counter = 0;
            }
        }

        System.out.println("\ntexts ready, writing to file");

        counter = 0;
        try (FileOutputStream output = new FileOutputStream(new File("C:\\temp\\bignumber.txt"))) {
            for (String text : threes) {
                output.write(text.getBytes());
                output.write(' ');

                // print progress
                if (counter++ > 999) {
                    output.write('\n');
                    System.out.print(".");
                    counter = 0;
                }
            }
        }

        System.out.println("\ndone");
    }

}