回复 150楼 吹水佬
先从第四点,说起:这个问题无非就是做个多么大的筛子,它仍就没有离开筛法的本质。在以2为周期时,只有2n-1,可能是素数;当增到周期6时,即能过素数2,和3的式子,只有6n-5,6n-1,两个式子;当把素数5也拽进来时,只有1,7,11,13,17,19,23,29这八类式子,它们加30n,一直都会有素数产生;说白了,就是素数连成积(素数阶乘)的互质数,所形成的多项式,210n+与210互质的数,共有(2-1)*(3-1)*(5-1)*(7-1)=48个,素数只能在这48个多项式式子中产成,.....,我的筛子,做到2*3*5*7*11*13*17=510510,一个周期的跨度就是510510个,自然数。所需要判断2*4*6*10*12*16=92160个数值,是否为素数,10个外循环,就可以跨过510510*10=5105100个自然数,需要判断92160*10=921600个数是否为素数。这里有个关键性问题,不是一个一个的判断,是否为素数,而是,一次性判断整个区间段内数,是否为素数,这里的一个外循环,是要判断92160个数是否为素数。当然,筛子还可以做大些,根据需要而定。那个数据源表,就是一个提前做出来的一个筛子。
当然这种做法,就一定会用到素数表,所以计划筛选多大范围,就需要其平方根前的素数表。
再说一下,第三点,我的意思不是那种的应用嫁接,还是用它处理同样的问题:
例如能过素数2,3,5的孪生素数对,(0,2),过素数2时,剩余1个可选,过素数3时,仍就一个可选(因为0除3余数为0,被占用,2除3余数为2,余数2被占用,只有模3余1的余数未被占用);(0,2)过素数5的关卡时,余数0,及余数2被占用,余数1,3,4可取,周期2*3*5=30,(2-1)*(3-2)*(5-2)=3,也就是说,在30周期这个跨度内,只有三个数可以通过:分别为1,13,19.
素数 2 3 5
0 0 0 0
2 0 2 2
剩余余数类 1 1 1
剩余余数类 3
剩余余数类 4
横竖说明 对素数2 对素数3 对素数5
选项 1
选项 7
选项 1 13
选项 1 3 19
选项 2 5 25
可选项 1 1 1
可选项 13
可选项 19
如果不去专门研究,或许得好好理解一下,在30以内,只有30n+1,30n+13,30n+19这三个式子可以产生孪生素数对(用最后一个表示)。
当扩展到,素数7时,仍就需要去掉余数0及余数2,那么30*7=210内,符合条件的,有3*(7-2)=15个式子,可以产生孪生素数对,
周期210 0 30 60 90 120 150 180
1 1 31 61 91 121 151 181
13 13 43 73 103 133 163 193
19 19 49 79 109 139 169 199
先按素数5时,周期30,向后扩展,3*7=21个元素,其中有3*2=6个元素,过不了素数7的关卡。即上边模7余数为0,或者2的。
周期210 0 30 60 90 120 150 180
1 1 31 61 0 0 151 181
13 13 43 73 103 0 0 193
19 19 0 0 109 139 169 199
模7余数是0或2的数置数成0,其余的照搬。
素数问题的解决是我学习编程永恒的动力。