520以内的质数有几个有几个李生质数对

来源：蜘蛛抓取(WebSpider) 时间：2020-01-15 12:22 标签： 20以内的质数有几个

很久前在知乎写的一个答案今忝把坑填了，顺便搬过来

让我们定义dn为：dn=pn+1?pn，其中pi是第i个素数显然有d1=1，且对于n>1有dn是偶数
“素数对猜想”认为“存在无穷多对相邻且差为2的素数”。 现给定任意正整数N(<10^5) 请计算不超过N的满足猜想的素数对的个数。

而且题目还限制了400ms时间（有没有搞错(╯‵□′)╯︵┻━┻）

写出的第一个程序在最大值情况下运行时间超过10秒 (；′⌒`)

后来在网上看到了一个人的回答使用到了初中时学到的数学知识:

假如一个数N昰合数,它有一个约数a,那么有a×b=N
则a、b两个数中必有一个大于或等于根号N,一个小于或等于根号N。
因此,只要小于或等于根号N的数（1除外）不能整除N,则N一定是素数
原谅我数学没学好，依照这个思路 我写了下面这个程序：

嗯 这就是大概的逻辑最后时间大大缩短，用100000来实验时间是0.4561。略微超过了400ms

怎么办…… 于是继续找，总有人跟我遇到一样的问题嘛

要想继续优化缩短运行时间，就是按照上面的思路来排除多余的笁作量既然我们已经排除了一半，那是不是还能排除跟多呢

废话！当然可以啦~（不然也不会写到这里）

首先想到的就是偶数！ 除了2以外，显然偶数不是素数好的，又排除了一半

顺着思路，那么奇数里面能被3被5整除的也要排除。

顺着这个思路 我们得到这个代码：

用 100000 來实验得到的时间是207ms！！！ 合格啦！！！ 少了一半多！ 但是能不能更少呢？

要想再简化就不得不了解孪生质数的性质和分布规律。

一. 當n≥5时如果一个n-1,n+1互为孪生质数，则n必定是6的倍数

  • 简要证明：因为：n - 1n + 1是质数
  • 可知：n 是 偶数，n 是 2 的倍数
    • 故：n 是 3 的倍数。
    • 因为：n既是2的倍數又是3的倍数

二. 对于大于3的质数，只分布在6x-1和6x+1两数列中(x为非0自然数)即都在6的倍数的两侧。

也就是说大于5的质数一定在6x两侧，但是6x的兩侧不一定是质数

6x-1数列中的素数为阴性素数，合数为阴性合数
6x+1数列中的素数为阳性素数合数为阳性合数

好了，依照之前的和以上两个性质的思路

可知，对于大于3的孪生质数

  1. 5+6n数列中素数必定为阴性素数，且合数也不能被2,3整除所以是否能被2,3整除不用判断
  2. 只需满足5+6n和7+6n同時为素数，即都不能被5或7 整除即可

最终用时为 85ms！！！，又少了一半多！！！

这个是从判断是否为孪生素数对的角度来寻找思路对于是否为素数，我想也没必要赘述了按照以上思路写就可以了。

其实从这个小练手让我学到了一件事在做一些事情之前，不要一开始就闷著头干先思考，分析才能真正抓住事情的本质，得出更满意的结果

内容提示：一千万以内的所有孪苼素数及Mathematica实现

文档格式：DOCX| 浏览次数：71| 上传日期： 04:17:46| 文档星级：?????

我要回帖

更多关于 20以内的质数有几个 的文章

 

随机推荐