[原创]最先进的素数计算方法

wangzc1634 · 发表于 2008-7-27 23:08

[watermark]最先进的素数计算方法
是不是最先进，只有亲自体会了，才会知道其中的奥妙！
为什么说是最先进的？因为，人们知道：在素数筛选中，删除频率最高的是小素数，我们采取逐步排除所有小素数删除的方法，简化筛法；在我的计算中，删除数永远低于剩余数，随着排除素数删除因子的不断增大，删除数与剩余数的比例越来越小；删除数是直接进行计算得到，用不着动脑筋去寻找删除数；得到删除数后，在对具体数的删除时，也有快速高效的方法。本方法可以直接投入素数的计算，简单易学。
对任何素数删除因子的删除都是一次性排除，一旦排除该素数删除因子的删除后，在后面的整个自然数中，永远不会存在该素数删除因子倍数的数字，即该素数的删除数了。该计算方法，为素数的整体计算，不会遗漏任何一个素数；该计算方法，又是不重复计算方法，不论是可生成素数的数，还是删除数，都不会出现重复。
我们采取逐步排除小素数删除的方法，排除素数删除因子：2、3、5、7、11、13、……N。我们用不着都写出来，简称排除N。
1、排除素数2的删除：小于2且不能够被2整除的数为1，简称不能整除数（下同，下面所说的不能整除数是指：不能被小于素数N的所有素数整除的数），用不能整除数作首项，用素数删除因子之积作为公差，这里所说的素数删除因子之积是指素数N及小于N的所有素数之积。排除素数2的删除后，有等差数列2X+1，X为自然整数，即等差数列2X+1的所有项都不能够被素数2整除（删除），即为排除了素数2的删除；
2、排除素数3的删除：在上面等差数列中取3项，即与这里的素数等值的项数，有：1，3，5。用上面的不能整除数乘以这里的素数为删除数：1*3=3，将3从这三项中删除，剩1，3为新等差数列的首项，用素数删除因子之积作公差：2*3=6，有6X+1，6X+5；
3、排除素数5的删除：用上面的不能整除数乘以素数5有：1*5=5，5*5=25，从下面的数列中删除。在上面2个等差数列中，各取5项：
6X+1有：1，7，13，19，25，删除25，
6X+5有：5，11，17，23，29，删除5，
这里剩余数为首项，用素数删除因子之积作公差6*5=30，组成30X+1，30X+7，30X+11，30X+13，30X+17，30X+19，30X+23，30X+29，组成了8个等差数列；
4、排除素数7的删除：用上面的不能整除数乘以素数7有：1，7，11，13，17，19，23，29分别乘以7为：7，49，77，91，119，133，161，203从下面的等差数中删除。在上面的等差数列中各取7项为：
30X+1，有：1，31，61，91，121，151，181，删除91，
30X+7，有：7，37，67，97，127，157，187，删除7，
30X+11，有：11，41，71，101，131，161，191，删除161，
30X+13，有：13，43，73，103，133，163，193，删除133，
30X+17，有：17，47，77，107，137，167，197，删除77，
30X+19，有：19，49，79，109，139，169，199，删除49，
30X+23，有：23，53，83，113，143，173，203，删除203，
30X+29，有：29，59，89，119，149，179，209，删除119，
用这里删除后剩余数为首项，用素数删除因子之积作公差30*7=210，组成48个等差数数；
5、排除素数11的删除：用上面剩余的48个数乘以11有：11，121，341，451，671，781，1111，1331，1441，1661，1991，2101；187，407，517，737，1067，1177，1397，1507，1727，1837，2057，2167；143，253，473，583，803，913，1133，1243，1573，1793，1903，2123；209，319，649，869，979，1199，1529，1639，1859，1969，2189，2299。从下面的等差数列中删除。这么多删除数，那么多等差数列，看得眼花缭乱的，如何删除呢？因为，这里都是等差数列，公差是一样的，我们把所有项与第一项的差数计算出来，用这里的删除数减去差数，得出首项数，就从那一个数列寻找删除数。这里的相差数为：
210X：210，420，630，840，1050，1260，1470，1680，1890，2100，如删除2299，用2299-2100=199，我们就从210X+199的等差数列中进行寻找。
在上面48个等差数列中各取11个项：
210X+1，有：1，211，421，631，841，1051，1261，1471，1681，1891，2101，删除2101，
210X+11，有：11，221，431，641，851，1061，1271，1481，1691，1901，2111，删除11，
210X+31，有：31，241，451，661，871，1081，1291，1501，1711，1921，2131，删除451，
210X+41，有：41，251，461，671，881，1091，1301，1511，1721，1931，2141，删除471，
210X+61，有：61，271，481，691，901，1111，1321，1531，1741，1951，2161，删除1111
210X+71，有：71，281，491，701，911，1121，1331，1541，1751，1961，2171，删除1331，
210X+101，有：101，311，521，731，941，1151，1361，1571，1781，1991，2201，删除1991，
210X+121，有：121，331，541，751，961，1171，1381，1591，1801，2011，2221，删除121，
210X+131，有：131，341，551，761，971，1181，1391，1601，1811，2021，2231，删除341，
210X+151，有：151，361，571，781，991，1201，1411，1621，1831，2041，2251，删除781，
210X+181，有：181，391，601，811，1021，1231，1441，1651，1861，2071，2281，删除1441，
210X+191，有： 191，401，611，821，1031，1241，1451，1661，1871，2081，2291。删除1661，
210X+17，有：17，227，437，647，857，1067，1277，1487，1697，1907，2117，删除1067，
210X+37，有：37，247，457，667，877，1087，1297，1507，1717，1927，2137，删除1507，
210X+47，有：47，257，467，677，887，1097，1307，1517，1727，1937，2147，删除1727，
210X+67，有：67，277，487，697，907，1117，1327，1537，1747，1957，2167，删除2167，
210X+97，有：97，307，517，727，937，1147，1357，1567，1777，1987，2197，删除517，
210X+107，有：107，317，527，737，947，1157，1367，1577，1787，1997，2207，删除737，
210X+127，有：127，337，547，757，967，1177，1387，1597，1807，2017，2227，删除1177，
210X+137，有：137，347，557，767，977，1187，1397，1607，1817，2027，2237，删除1397，
210X+157，有：157，367，577，787，997，1207，1417，1627，1837，2047，2257，删除1837，
210X+167，有：167，377，587，797，1007，1217，1427，1637，1847，2057，2267，删除2057，
210X+187，有：187，397，607，817，1027，1237，1447，1657，1867，2077，2287，删除187，
210X+197，有：197，407，617，827，1037，1247，1457，1667，1877，2087，2297，删除407，
210X+13，有：13，223，433，643，853，1063，1273，1483，1693，1903，2113，删除1930，
210X+23，有：23，233，443，653，863，1073，1283，1493，1703，1913，2123，删除2123，
210X+43，有：43，253，463，673，883，1093，1303，1513，1723，1933，2143，删除253，
210X+53，有：53，263，473，683，893，1103，1313，1523，1733，1943，2153，删除473，
210X+73，有：73，283，493，703，913，1123，1333，1543，1753，1963，2173，删除913，
210X+83，有：83，293，503，713，923，1133，1343，1553，1763，1973，2183，删除1133，
210X+103，有：103，313，523，733，943，1153，1363，1573，1783，1993，2203，删除1573，
210X+113，有：113，323，533，743，953，1163，1373，1583，1793，2003，2213，删除1793，
210X+143，有：143，353，563，773，983，1193，1403，1613，1823，2033，2243，删除143，
210X+163，有：163，373，583，793，1003，1213，1423，1633，1843，2053，2263，删除583，
210X+173，有：173，383，593，803，1013，1223，1433，1643，1853，2063，2273，删除803，
210X+193，有： 193，403，613，823，1033，1243，1453，1663，1873，2083，2293，删除1243，
210X+19，有：19，229，439，649，859，1069，1279，1489，1699，1909，2119，删除649，
210X+29，有：29，239，449，659，869，1079，1289，1499，1709，1919，2129，删除869，
210X+59，有：59，269，479，689，899，1109，1319，1529，1739，1949，2159，删除1529，
210X+79，有：79，289，499，709，919，1129，1339，1549，1759，1969，2179，删除1969，
210X+89，有：89，299，509，719，929，1139，1349，1559，1769，1979，2189，删除2189，
210X+109，有：109，319，529，739，949，1159，1369，1579，1789，1999，2209，删除319，
210X+139，有：139，349，559，769，979，1189，1399，1609，1819，2029，2239，删除979，
210X+149，有：149，359，569，779，989，1199，1409，1619，1829，2039，2249，删除1199，
210X+169，有：169，379，589，799，1009，1219，1429，1639，1849，2059，2269，删除1639，
210X+179，有：179，389，599，809，1019，1229，1439，1649，1859，2069，2279，删除1859，
210X+199，有：199，409，619，829，1039，1249，1459，1669，1879，2089，2299，删除2299，
210X+209，有：209，419，629，839，1049，1259，1469，1679，1889，2099，2309。删除209，
将上面不能够整除数480个作为等差数列首项，公差为上面公差*11=210*11=2310，组成480个能够生成素数的等差数列。这48个等差数列意味着什么呢？如果说，我们不进行上面的排除，公差为2310可以组成1155个奇数数列，相当于减少了675个大于2310不能够产生素数的等差数列。减少了一多半的删除量，随着排除数的不断增多，减少的删除量会越来越大。
………………。
我们在这里，只讲素数的计算方法。这里将素数删除因子排除到素数11，那么，小于13*13=169的数字，加上排除的素数删除因子，都全部是素数，而且，小于2310的全部素数都在这其中，没有一个漏掉的。如果说，我们排除到素数删除因子79时，小于83*83=6889的数字全部都是素数，而且，32位数以内的全部素数都在其中。
如果说，我们排除到某一个删除因子时，不想继续排除下去了，我们可以把其它删除因子的删除数，全部进行删除，剩余的就都是素数。具体删除方法如下：
因为，我们排除到最后，只是首项不同，公差相同的多个等差数列。我们对每一个素数删除因子，都可以采取下面的计算方法，进行删除。
按余数寻找删除数：
比如说：素数11对公差为210的等差数列的删除，用210X+1先计算出下面的排列关系：
11个连续项为： 1， 211，421，  631，841，1051，1261，1471，1681，1891，2101，
除11对应余数： 1， 2， 3， 4， 5，  6， 7， 8， 9，  10，  11，
分别除以11为：0.09，0.18，0.27，0.36，0.45，0.54，0.63，0.72，0.81，0.9， 0，
这是一个特殊的素数与公差的关系，各项的余数与项数相同。我们再任意用相同的素数与公差的等差数列看删除项，求等差数列210X+17素数11的删除项。因为首项为17，17/11余数为0.54，为上面的第6项，上面11项为删除项，有11-6+1=6项，即素数11对210X+17等差数列的删除项为11Y+6项；
求等差数列210X+19素数11的删除项。因为，首项19/11余数为0.72，为上面的第8项，上面11项为删除项，有11-8+1=4项，即素数11对210X+19等差数列的删除项为11Y+4项；
求等差数列210X+23素数11的删除项。因为，首项23/11余数为0.09，为上面的第1项，上面11项为删除项，有11-1+1=11项，即素数11对210X+23等差数列的删除项为11Y+11项；
前面为删除项大于任何项的寻找方法，下面再讨论一下删除项小于其它项的借鉴方法。
比如说：再谈素数11对公差为210的等差数列的删除，用210X+11作为基础的计算。
等差数列的项： 1，  2， 3， 4， 5，  6， 7， 8， 9，  10， 11，
11个连续项为：11，221，431，641，851，1061，1271，1481，1691，1901，2111，
除11对应余数：0， 1， 2， 3， 4， 5，  6， 7， 8， 9，  10，
分别除以11为：0，0.09，0.18，0.27，0.36，0.45，0.54，0.63，0.72，0.81，0.9，
根据上面的余数与项的关系，计算210X+29的删除项。因为，29/11余数为0.63为第8项，如果说，我们还用上面的减法，肯定减不够。210X+11的删除项为第一项，那么，210X+11的下一个删除项为1+11=12项，根据前面的计算方法则有：（1+11）-8+1=5为素数11对210X+29的删除项，即11Y+5项为素数11对210X+29的删除项。
再计算素数11对210X+13的删除项，因13/11=0.18为第三项,有(1+11)-3+1=10项,则素数11对210X+13的删除项为:11Y+10项。
                           四川省三台县工商局：王志成
[/watermark]

刘合亮 · 发表于 2008-8-2 23:11

正确与否还不知道，怎能说先进呢？

wangzc1634 · 发表于 2008-8-3 18:19

正确与否，请进行检验！
如发现问题，或不能够理解的地方，敬请提出来讨论！
特别是任何一个问题，都必须有相应的理论或事实依据作为支撑点，才能够站得住足！

仙剑魔 · 发表于 2008-8-29 10:02

很先进,爱氏筛的改进版...理论是没有问题的
我1年前就会了,网上的达人更早,N年前就有人发帖了...
有人研究过,手工筛到7就差不多了(出于写代码的角度考虑)
去掉2的倍数可以减少1/2的数字,剩下1/2
再去掉3的倍数,只剩下1/6
一此类推...
到7的时候就差不多了,往后面优势不明显,因为代码越来越长的...
PS:这个显然不是最先进的方法,因为很大众化...

wangzc1634 · 发表于 2008-9-24 22:17

筛出2的倍数，剩余1/2的自然数；筛出2，3的倍数剩余1/3自然数；筛出2，3，5的倍数剩余4/15的自然数。
这是确定了的定数，不是你所说的结果！

moranhuishou · 发表于 2008-9-27 13:04

筛法是最原始最直观但也是最笨最慢的方法！

a814153 · 发表于 2008-9-28 13:30

比如说，要筛到n＝2^48456283-1,用wangzc1634先生的筛法应该也要十万八千年，我估计。

moranhuishou · 发表于 2008-9-28 17:21

  试除法搜素数:

20位数    2小时
50位 10^11年
100位 10^36年
200位 10^86年
1000位  10^486年
2^48456283-1是1200多万位！
没法比的。

Bardo · 发表于 2008-10-4 18:15

很多年前在我的个人网站东方热讯论坛，我发过这样的VB代码。100000以内超快。
但是到11位数时，就是不很快了

njzzyy · 发表于 2008-10-14 22:53

首先要祝贺楼主!!!
不管以前是否有人想到过,介绍过,楼主这种钻研精神可贵
建议:尽量用符号简化叙述过程,这样更数学化

		自动登录	找回密码
密码			注册

[原创]最先进的素数计算方法