[原创]自然复筛法与爱氏筛法的比较

shihuarong1

[watermark]     
                        自然复筛法与爱氏筛法的比较
   爱氏筛法（Eratosthenes)大家都很熟悉。设有偶合数N=2n,则用不大于√N的全部素数（其中最大的一个素数为Pk)对数列[1,2n]筛选后，所留下的数,除“1”以外，全部都是素数。
     如果将数列[1,N]在n点对折，则构成由n个等和数对组成的“折n数列”，相应的等和数对之和都是等于N .折n数列是一个复合数列，但是为了方便我们用简单数列[1,n]表示，
[n,N]区间的数不需要写出来。
     我们发现：爱氏筛法可以筛除[1,N]区间的所有和数，留下素数（这里“1”也视为素数。而自然复筛法可以筛除折n数列中包含的合数对，而把素数对全部留下来。
  现以偶数N=34为例，用的筛选元素与一筛方法和爱氏筛法相同。二筛的消项因子R1=1;
  R2=4 ,.区间是[1,17] 第一步先复筛P0=2,筛后留项是奇数数列[1,17].第二步复筛P1=3,
   筛后留项是3, 5  11  17. 第三步复筛P2=5,R2=4，没有消项。所以留下的4个数对都是“等和素数对”。把与它们配对的素数写出来，就有3+31=5+29=11+23=17+17，共4对。一点不差。
     更详细的资料请看”哥猜难题圆满破解“一文。[/watermark]

wangyangke

（笑话）继鲁思顺——定理：鲁思顺是个二百五！——之后，陕西雷明举重若轻，轻松证明哥德巴赫猜想