7

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

与此相关的问题之一是质数不能分解为因子。如果他们可以，这个问题会容易得多。

4

9 回答 9

9

如果你真的想将素数存储为数字和一个问题，阻止你的是“素数不能分解为因子”，还有另一件事：将它存储在按序列排序的任何数字的模数列表中。

小例子：

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

清单是：

81, 17, 83, 2

在实际应用中，按 2^32（32 位整数）的模数进行拆分很有用，特别是在处理应用程序中存储为字节数组的素数时。

数据库中的存储：

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
于 2009-12-16T13:54:27.993 回答
6

您可以将它们存储为二进制数据。它们不会直接从数据库中被人类读取，但这不应该是一个问题。

于 2009-12-15T13:25:48.947 回答
5

数据库（取决于哪个）通常可以准确地存储高达 38-39 位的数字。这让你走得很远。

除此之外，您将不会在数据库中（准确地）对它们进行算术运算（除非您的特定数据库可能存在任意精度的模块）。但是数字可以存储为多达几千位的文本。除此之外，您还可以使用 CLOB 类型字段来存储数百万位数字。

此外，如果您正在存储素数序列并且您对该序列的空间压缩感兴趣，那么您可以从存储一个数字与下一个数字之间的差异而不是整数开始，这也是毫无价值的。

于 2009-12-15T13:26:10.117 回答
4

这有点低效，但您可以将它们存储为字符串。

于 2009-12-15T13:23:29.327 回答
3

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

于 2009-12-15T13:24:36.177 回答
3

这是我的 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，但我不确定您为什么要打扰。

于 2009-12-15T17:14:26.460 回答
2

这完全取决于您要对这些数字进行何种操作。如果只是存储和查找，那么只需使用字符串并使用检查约束/域数据类型来强制它们是数字。如果您想要更多控制权，那么 PostgreSQL 将允许您定义自定义数据类型和函数。例如，您可以与GMP库接口，以对任意精度整数进行正确的排序和算术运算。使用这样的库甚至可以让您实现一个检查约束，该约束使用概率素数测试来检查数字是否真的是素数。

真正的问题实际上是关系数据库是否是完成这项工作的正确工具。

于 2009-12-15T16:34:32.530 回答
0

我认为你最好使用 BLOB。数据在 BLOB 中的存储方式取决于您对数字的预期用途。如果你想在计算中使用它们，我认为你需要创建一个类或类型来将值存储为某种有序的二进制值，并允许它们被视为数字等。如果你只需要显示它们然后将它们存储为字符序列就足够了，并且无需将可计算的值转换为可显示的值，这对于较大的值可能非常耗时。

分享和享受。

于 2009-12-15T15:56:15.933 回答
0

可能不是很出色，但是如果您将它们存储在一些递归数据结构中会怎样。您可以将其存储为 int、指数和对低位数字的引用。

就像字符串的想法一样，它对于内存考虑可能不是很好。由于查询的递归性质，查询时间会增加。

于 2009-12-15T16:31:26.127 回答