首页 文章

在数据库中存储大质数

提问于
浏览 次
7

这个问题让我觉得有些奇怪 . 我很好奇你如何能够代表数据库中的素数列表 . 我不知道单个数据类型是否能够精确且一致地存储大量素数 . 我担心的是，当素数开始包含1000个数字时，从数据库中引用可能有点困难 . 有没有办法在DB中表示大量素数？我很确定这个主题已经接近过了 .

关于这个问题的一个问题是，质数不能分解为因素 . 如果他们能解决这个问题就容易多了 .

mysql database oracle postgresql primes

9 回答

  • 1

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

    小例子：

    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
    回复于
  • 0

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

    回复于
  • 5

    数据库（取决于哪些数据库）可以例行地准确存储高达38-39位的数字 . 这让你合情合理 .

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

    此外，如果您存储素数序列并且您对该序列的空间压缩感兴趣，则可以从存储一个数字与下一个数字之间的差异而不是整数来开始，这是没有 Value 的 .

    回复于
  • 0

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

    回复于
  • 3

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

    回复于
  • 9

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

    但你真的不想这样做，你想要存储超出任何整数数据类型的humongous（sp？）素数方式 . 而且你说你反对字符串所以它是你的二进制数据 . （也适合我 . ）是的，您可以将它们存储在数据库中的BLOB中，但是DBMS会为您提供哪种设施来查找第n个素数或检查候选整数的优先级？

    如何设计合适的文件结构？这是我在约5分钟后想出的最好的想法：

    • 将计数器设置为2 .

    • 写入代表第一个素数的两位 .

    • 再次写入它们，以标记包含2位素数的部分的结尾 .

    • 将计数器设置为计数器1

    • 按顺序写入3位素数 . （我认为有两个：5和7）

    • 再次写入最后一个3位素数以标记包含3位素数的部分的结尾 .

    • 回到4并经过必要的修改后继续进行 .

    关于编写最后一个n位素数两次的观点是，当你来读取文件时，为你提供一种方法来识别文件中有n位素数的部分的结尾 .

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

    我认为这会起作用，它会处理最多2 ^（你可以表示的最大无符号整数）的素数 . 我想很容易找到将325467位（比方说）值转换为大整数的代码 .

    当然，你可以将这个文件存储为BLOB，但我不确定你为什么这么做烦 .

    回复于
  • 4

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

    真正的问题实际上是关系数据库是否是正确的工具 .

    回复于
  • 3

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

    分享和享受 .

    回复于
  • 6

    可能并不精彩，但如果将它们存储在一些递归数据结构中会怎样 . 您可以将其存储为int，它是指数，以及对较低位数的引用 .

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

    回复于

相关问题