时间戳

首页 > 解决方案 > 梅森素数处理

sql - 梅森素数处理

问题描述

我对 Mersenne Primes 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，它可以存储多达 10 亿个。但它不能用于计算。

Postgres 提供的东西足以满足任何实际需求。我的问题是 GIMPS 的人如何计算如此大的数字。他们是否将这些数字存储在任何数据库中。哪个数据库支持这么大的数字。我是否与数据库世界取得的进展不同步。

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

好奇而已。这听起来像我失业了。

谢谢

bb23850

标签： sqlpostgresqlbigint

解决方案

梅森数很容易计算。它们总是小于 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 个梅森数之前，穷举搜索就变得不可行了。

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

推荐阅读