在数据库中存储大素数

StackOverflow https://stackoverflow.com/questions/1907409

题

这个问题让我觉得有点奇怪。我很好奇如何在数据库中表示素数列表。我不知道有哪种数据类型能够准确且一致地存储大量素数。我担心的是，当素数开始包含数千位数字时，从数据库中引用可能会有点困难。有没有办法在数据库中表示大量素数？我很确定以前已经讨论过这个话题。

造成这一问题的困难之一是素数不能分解为因数。如果他们可以的话，这个问题就会容易得多。

有帮助吗？

解决方案

如果你真的想存储素数数字和的问题之一，停止你的是“质数不能被分解成因素”外，还有另一件事：它存储在由顺序排列的任何数量的模量的列表。

小示例：

2831781 == 2*100^3 + 83*100^2 + 17*100^1 + 81*100^0

列表是：

81, 17, 83, 2

在实际应用中是有用的由2 ^ 32（32位整数）的模数来分割，特别是如果在处理的应用程序的素数存储为字节阵列。

存储在DB：

create table PRIMES
(
  PRIME_ID         NUMBER not null,
  PART_ORDER       NUMBER(20) not null,
  PRIME_PART_VALUE NUMBER not null
);

alter table PRIMES 
add constraint PRIMES_PK primary key (PRIME_ID, PART_ORDER) using index;

插入例如上述（1647是例如仅）：

insert into primes(PRIME_ID, PART_ORDER, PRIME_PART_VALUE) values (1647, 0, 81);
insert into primes(PRIME_ID, PART_ORDER, PRIME_PART_VALUE) values (1647, 1, 17);
insert into primes(PRIME_ID, PART_ORDER, PRIME_PART_VALUE) values (1647, 2, 83);
insert into primes(PRIME_ID, PART_ORDER, PRIME_PART_VALUE) values (1647, 3, 82);

prime_id值可以从Oracle序列被分配... 

create sequence seq_primes start with 1 increment by 1;

要插入下一素数的获取ID：

select seq_primes.nextval from dual;

选择素数与内容指定id：

select PART_ORDER, PRIME_PART_VALUE 
from primes where prime_id = 1647 
order by part_order

其他提示

您可以将它们保存为二进制数据。他们不会从数据库中人类可读的直线，但不应该是一个问题。

数据库（取决于哪个）可以常规存储号码可达38-39位准确。这让你相当远。

除此之外，你不会对他们（精确）数据库中（不包括可能存在于您的特定数据库的任意精度的模块）做算术运算。但是号码可以存储为文本可达几千位。除此之外，您可以使用CLOB类型字段存储的数字百万。

此外，它没有价值，如果你存储素数的序列和你的兴趣是按照这个顺序，你可以通过存储一个序号，下一个，而不是整个数之差开始的空间压缩。

这是有点低效率的，但你可以将它们存储为字符串。

如果您不打算使用的数据库端计算与这些数字，只是将它们存储为它们的二进制表示的比特序列（BLOB，VARBINARY等）

这是我的 2 美分价值。如果您想将它们作为数字存储在数据库中，那么您将受到数据库可以处理的最大整数大小的限制。您可能需要一个 2 列的表，其中一列是素数，另一列是序号。然后您需要一些索引来快速查找存储的值。

但你并不是真的想这样做，对吗？你想存储巨大的（sp？）素数，远远超出你所拥有的任何整数数据类型。你说你不喜欢字符串，所以它对你来说是二进制数据。（这也适合我。）是的，您可以将它们存储在数据库中的 BLOB 中，但是 DBMS 将为您提供什么类型的工具来查找第 n 个素数或检查候选整数的素数？

如何设计合适的文件结构？这是我思考了大约 5 分钟后能想到的最好的结果：

  1. 将计数器设置为 2。
  2. 写入代表第一个素数的两位。
  3. 再次写入它们，以标记包含 2 位素数的部分的结尾。
  4. 将计数器设置为 counter+1
  5. 按顺序写出 3 位素数。（我认为有两个：5 和 7)
  6. 再次写入最后一个 3 位素数，以标记包含 3 位素数的部分的结尾。
  7. 返回4并进行必要的必要修改。

将最后一个 n 位素数写入两次的目的是为您提供一种方法，以便在您读取文件时识别文件中包含 n 位素数的部分的末尾。

当您编写文件时，您可能还需要记下文件中各个点的偏移量，也许是包含 n 位素数的每个部分的开头。

我认为这可行，并且它可以处理最多 2^（可以表示的最大无符号整数）的素数。我想很容易找到将 325467 位（比如说）值转换为大整数的代码。

当然，您可以将此文件存储为 BLOB，但我不确定您为什么要麻烦。

这一切都取决于你想要的数字做什么样的操作。如果只是存储和查找，然后只使用字符串和使用检查约束/域的数据类型来实施他们的数字。如果你想要更多的控制，那么PostgreSQL将让你定义自定义数据类型和功能。您可以使用 GMP 库实例接口有任意精度的整数正确排序和算术。使用这样的库，甚至可以让你实现使用概率素性测试，以检查如果数字真的是首要检查约束。

真正的问题其实是一个关系型数据库是否适合工作的正确工具。

我觉得你最好使用BLOB。如何将数据存储在您的BLOB取决于你的使用目的的数字。如果你想在计算中使用他们，我认为你需要创建一个类或类型的值存储为一些品种有序二进制值，并允许它们被处理为数字，等等。如果你只是想显示他们，那么它们存储作为一个字符序列就足够了，并且将不再需要你的可计算的值转换为可显示的东西，这是非常耗时的大值。

共享和欣赏。

也许并不光彩，但如果你将它们存储在一些递归数据结构是什么。你可以将其存储为一个int，它的指数，并于低位数的参考。

像串的想法，它可能不会是内存的考虑非常好。和查询时间将增加，由于该查询的递归性质。

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top