如何打印迄今为止找到的最大素数？

Question

1 月 19 日，一项新的世界纪录诞生了：迄今为止发现的最大质数之一。该数字总计 2^74207281 - 1，有超过 2230 万位。我在 youtube 的 numberphile 频道上看到他们将这个数字印在一本由 3 部分组成的书中。现在我的问题是：如何获得如此大的数字的字符串表示形式？显然这会花费一些时间，但最有效的方法是什么？

我知道在 Java 中执行此操作的唯一方法是使用 BigIntegers，这是最好的方法吗？用其他语言怎么样？

Answer 1

The only way I would know to do this in Java is by using BigIntegers, is this the best way?

简而言之

您问题的答案是：是。

详细

我认为 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");
    }

}

Answer 2

在将其打印到文件之前，您实际上不需要将整个数字存储为字符串。你只需要一个一个地输出每个数字。

至于在内存中表示数字本身；那是另一回事。有一些有效的方法可以存储和操作大量的 Mersenne 形式：您不想依赖罐装大整数 class（例如 Java 中的 BigInteger）来执行此操作。素性测试所需的数学运算太慢了。

GIMP 项目中有更全面的详细信息。参见 http://www.mersenne.org/

Answer 3

在 Linux 系统上很容易实现：

echo "2 74207281 ^ 1 - p" | dc > /tmp/74207281.txt

该文件大小约为 22 MB，这不足为奇。在 i7 上，计算大约需要 45 分钟。时间不准确。

顺便说一下，根据梅森定理，74207281 本身也是素数。

如何打印迄今为止找到的最大素数？

How to print the largest prime number found so far?

java

string

primes

biginteger