J 素数枚举

Question

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

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

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

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

Answer 1

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

NOTE! This is speculation, based on benchmarks (shown below).

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

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页面指​​出:

Currently, arguments larger than 2^31 are tested to be prime according to a probabilistic algorithm (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 */