在数据库中存储大质数

Question

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

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

Answer 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

Answer 2

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

Answer 3

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

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

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