zhangJW_cn 阅读(941) 评论(16)
     很久没有记录什么了,但是最近又没有什么值得记录的,想copy过来的又介于非技术,想写又不好写的也不便写在这里。

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

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

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

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

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

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

所以两个定义是等价的,根本不用猜测
清风雨
re: 关于质数(素数)的算法
对。合数必然有质因数,所以,证明了。
谢谢!
perry
re: 关于质数(素数)的算法

素因数分解是一个NP问题。
perry
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方法。





发表评论
切换编辑模式