j - J 素数枚举

Question

J 将通过 p:n 回答第 n 个素数。

如果我要求第 1 亿个素数，我几乎可以立即得到答案。我无法想象 J 会那么快地筛选那个素数，但也没有在表中查找它，因为该表的大小约为 1GB。

有一些方程给出了质数数量的近似值，但它们只是近似值。

J怎么这么快就找到答案了？

Answer 1

J用一张表开始，然后计算

笔记！这是基于基准的推测（如下所示）。

如果您想自己快速尝试，请尝试以下操作：

p:1e8   NB. near-instant
p:1e8-1 NB. noticeable pause

图上的低点是 J 在表格中查找素数的位置。之后，J将从特定起点计算值，因此它不必计算整个事物。所以一些幸运的素数将是常数时间（简单的查表），但通常首先是查表，然后是计算。但令人高兴的是，它从上一个表查找开始计算，而不是计算整个值。

基准

我做了一些基准测试，看看p:我的机器（iMac i5，16G RAM）的性能如何。我正在使用J803。结果很有趣。我猜时间图中的锯齿模式（在“高达 2e5”图中可见）与查找表相关，而整体对数形状（在“高达 1e7”图中可见）与 CPU 相关。

NB. my test script
ts=:3 : 0
  a=.y
  while. a do.
  c=.timespacex 'p:(1e4*a)'  NB. 1000 times a
  a=.<:a
  b=.c;b
  end.
  }:b
)

a =: ts 200

require'plot'
plot >0{each a  NB. time
plot >1{each a  NB. space

（p:最多 2e5）

时间

空间

（p:最多 1e7）

时间

空间

在这些运行期间，一个核心在 100% 左右徘徊：

此外，voc页面指出：

目前，大于 2^31 的参数根据概率算法 (Miller-Rabin) 被测试为素数。

除了@Mauris 指出的主要查找表之外，v2.c还包含以下功能：

static F1(jtdetmr){A z;B*zv;I d,h,i,n,wn,*wv;
 RZ(w=vi(w));
 wn=AN(w); wv=AV(w);
 GA(z,B01,wn,AR(w),AS(w)); zv=BAV(z);
 for(i=0;i<wn;++i){
  n=*wv++;
  if(1>=n||!(1&n)||0==n%3||0==n%5){*zv++=0; continue;}
  h=0; d=n-1; while(!(1&d)){++h; d>>=1;}
  if     (n< 9080191)*zv++=spspd(31,n,d,h)&&spspd(73,n,d,h);
  else if(n<94906266)*zv++=spspd(2 ,n,d,h)&&spspd( 7,n,d,h)&&spspd(61,n,d,h);
  else               *zv++=spspx(2 ,n,d,h)&&spspx( 7,n,d,h)&&spspx(61,n,d,h);
 }
 RE(0); R z;
}    /* deterministic Miller-Rabin */