J Primes枚举

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

目前，根据概率算法（Miller-Rabin），大于2 ^ 31的自变量被测试为质数。

除了@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 */