梅森素数处理

Question

我对梅森素数感兴趣https://www.mersenne.org/。 Great Internet Mersenne Prime Search (GIMPS) 正在做这方面的研究。这些是质数，但非常大而且很少。第 49 个梅森素数的长度为 2200 万位。一个数能有2200万位，真是不可思议。

我试过了，可以赶上第 8 个梅森素数，长度为 10 位数，在 20 亿以内。我正在使用 Postgres BIGINT，它最多支持 19 位长整数，即 900 万亿。因此，如果我一次处理 10 亿行，则需要 900 万次迭代。我可以进一步使用支持小数点左侧 131072 位数字和精度 16383 位数字的 NUMERIC 数据类型。当然，我只需要使用整数。我不需要精确度。另一种选择是 Postgres 的 CHAR VARYING，它最多存储十亿个。但是不能用于计算。

Postgres 提供的内容足以满足任何实际需要。我的问题是 GIMPS 的人是如何计算如此大的数字的。他们是否将这些数字存储在任何数据库中。哪个数据库支持这么大的数字。我是否跟不上数据库世界的进步。

我知道他们拥有强大的处理能力 Curtis Cooper 提到有 700 台服务器被用来发现和验证这些数字。究竟需要多少存储空间。使用的是什么语言。

只是好奇。这听起来像是我失业了吗？

谢谢

bb23850

Answer 1

梅森数很容易计算。它们总是比 2 的幂小一：

select n, cast(power(cast(2 as numeric), n) - 1 as numeric(1000,0))
from generate_series(1, 100, 1) gs(n)
order by n;

挑战在于确定所得数字是否为素数。梅森知道 n 需要是质数，对应的梅森数才是质数。

计算机再快，一旦数字超过十几位或两打左右，要穷尽所有因素是行不通的。从上面的代码可以看出，在第 100 个 Mersenne number.

之前很久，穷举搜索就变得不可行了

为了确定这样的数字是否为素数，使用了很多数学方法——其中一些是为这个特定问题发明的或受其启发的。我很确定在关系数据库中实施任何这些素数测试都非常困难。

梅森素数处理

Mersenne Primes processing

sql

postgresql

bigint