关于质数（素数）的算法
zhangJW_cn 2014-4-7 15:43:00 阅读(1032) 评论(16)
     很久没有记录什么了，但是最近又没有什么值得记录的，想copy过来的又介于非技术，想写又不好写的也不便写在这里。

     前次遇到一个素数的问题，一直也想问问大家有没什么好的想法：计算从2到100000素数的个数，当然记录所有素数更好。希望用尽量少的内存和尽可能快的方法。

     1.定义
     根据素数定义，从2到100000遍历所有数字，每个数字根据定义判断是否素数。

     2.筛选
     先筛选掉所有的2的倍数（2倍），然后对剩余的数筛选3的倍数（2倍），从左至右依次遍历筛选。

     3.猜测（由于自己找不到证明，所以只能算猜测）
     素数是不能被素数整除的，虽然并不是不能被素数整除的数就是素数，但是，我们列举一些数就会发现，每个素数是不能被他之前的素数整除的，只需判断该数不能被他之前的素数整除即可。
     另外，任何一个数必定有比他的平方根小的因子，所以，可以只用判断到平方根以前的素数就够了（不过，因为求平方根比较毫时，这里实际也不必采用；同样，用前面的素数的平方比较也是不必的，乘法代价较这种遍历量小的情况实际更昂贵）。

评论列表
MemoryTime2014-4-7 15:43:00
re: 关于质数（素数）的算法
    2、3是素数，排除2、3的倍数，是肯定了“素数是不能被他之前的素数整除的”，所以2筛选与3猜测意义相同。
    假定了我们已经知道2、3为素数，所以可以假定我们知道更多的素数（7、11、13...)等，排除他们的倍数节省开平方消耗。
    讨论一下。
周星星2014-4-7 15:43:00
re: 关于质数（素数）的算法
素数是除了1和它自己……，当然不能被其他素数……了。
清风雨2014-4-7 15:43:00
re: pAnic
你给的计算素数的方法，正是猜测里说的。
但，不知道能不能证明这个猜测。
清风雨2014-4-7 15:43:00
re: MemoryTime 和 周星星
这个是必要命题，但不是充分命题。—— 至于这个被猜测的充分命题是否正确，现在也不能肯定（个人不能证明）。

MemoryTime的意思不太明白，猜测就是用的前面这个“所谓的”充分命题，然后对每个数只需要检测他前面的素数即可，你的意思是将猜测和筛选结合？
清风雨2014-4-7 15:43:00
re: 一笑
啊！ 我早知道就好了。 自己还想了好久，但是不知道怎么证明。
清风雨2014-4-7 15:43:00
re: 一笑
1.你的"爱沙托散筛法"，似乎就是定义筛选法。不知是我没看明白还是？
2.不知道“猜测”是正确的还是错误的。正确的，希望能看到证明；错误的，希望能给出反例。
3.你和pAnic的都给出类素数判断的好方法，不知道还有没谁有好方法，希望能得一见。
馨荣家园2014-4-7 15:43:00
re: 关于质数（素数）的算法
这种方法还要证明么？不就是素数定义么？
馨荣家园2014-4-7 15:43:00
re: 关于质数（素数）的算法
这种筛选法只适合小素数，而目前更重要得是获得大素数，例如宽度超过180位得素数。我得博客种有素数的计算算法，你可以去看看
清风雨2014-4-7 15:43:00
re: 关于质数（素数）的算法
素数的定义是：只能被本身和1整除的数。
猜测认为：任何一个不能被他前面的所有素数整除的数必定是素数。
比如7，他前面是5、3、2，所以7是素数；但是9能被他前面的3整数，所以不是；11又是，13是，15不是，17是，19是，......
arong2014-4-7 15:43:00
re: 关于质数（素数）的算法
清风雨的意思是不是：如果一个数不能被所有比他小的素数整除，你还需要猜测才能确定他是素数？

这个结论很显然啊？假设数a不是素数，那么肯定存在一个数b整除他

根据假设，所有小于他的素数都不能整除他，那么b一定是合数

1. 证明，合数的大于1的最小正因子肯定是素数
定义数b的正因子集合为B，则B-{1,b}肯定非空，否则b是一个质数

定义B' = B-{1,b}

假设r是B'中最小的元素，根据前面的结论，r肯定是存在的

假设r不是质数，那么r一定有个正因子r'，且1 < r' < r
但是r'必然也整除b，这和r是b是B'最小正元素的假设矛盾

结论是：r肯定是质数

2. 合数肯定有质数因子
有了结论1，这个结论显然

3. 回到原来问题，a能被一个合数b整除，但是不能被所有小于他的素数整除，这是不可能的，因为合数b的素数因子必然能整除a

所以两个定义是等价的，根本不用猜测
清风雨2014-4-7 15:43:00
re: 关于质数（素数）的算法
对。合数必然有质因数，所以，证明了。
谢谢！
perry2014-4-7 15:43:00
re: 关于质数（素数）的算法

素因数分解是一个NP问题。
perry2014-4-7 15:43:00
re: 关于质数（素数）的算法
为了在数字比较小时计算得快些，可以应用一些初等数论的结论：

1]
仅计算6n+1和6n+5（n=1,2,3,...）形式的数。易知6n+2和6n+4是2的倍数，6n+3是3的倍数。因为2和3的倍数最多。
2]
根据“合数的最大的素因数都不大于它的平方根”定理，每次分解仅算到被分解的平方根为止即可。
证明（一般的证明都不完整）：
设N=P*Q，P和Q是N的不少于1个素因数的乘积（指出这点很重要）。反证法可证P和Q都小于或等于N的平方根（否则P*Q>N）。等号当且仅当P=Q=N的平方根时成立（这时N是一个素数的平方）。

1]可减少2/3的计算量，2]可再减少1/2的计算量。即为原计算量的1/6。

几百位数位的数,建议采用ASK方法。





发表评论
切换编辑模式
您还没有登录,请[登录]或[注册]