J Primes枚举

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

如果我要求百万分之一的质数，我会得到几乎立即的答案。我无法想象J会如此迅速地筛选素数，但是在表中查找该表的大小都不会超过1GB。

有一些方程式给出了到边界的素数的近似值，但是它们只是近似值。

J如何如此迅速地找到答案？

最佳答案

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



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

关于J Primes枚举，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/29638573/