素数检测算法
需积分: 18 179 浏览量
2019-07-02
17:15:47
上传
评论
收藏 464KB PDF 举报
最近看到一则颇为有趣的新闻，说北大一名大一新生，以素数为标准选手机号，受到广大网友膜拜。其实素数的检测算
法是很有趣的，并且会涉及到数论、概率算法等诸多内容，一直觉得素数探测算法是了解概率算法很好的入口。本文和
大家简单聊聊如何确定一个数是素数。
素数
素数的定义
素数是这样被定义的：
一个大于1的整数，如果不能被除1和它本身外的其它正整数整除，则是素数（又称质数）。
与素数相关的定义还有合数：
一个大于1的整数，如果不是素数则是合数。其中能整除这个数的正整数叫做约数，不等于1也不等于合数本身的约数叫
做非平凡约数。
注意1既不是素数又不是合数。
举几个例子：
2是素数，因为除1和2外没有其它正整数可以整除2。
3也是素数。
4不是素数，因为2可以整除4。
11是素数，除1和11外没有正整数可以整除它。
15不是素数，3和5可以整除15。
素数的性质
素数有一些有趣的性质，下面不加证明的列几条。
素数有无穷多个。
设f(n)为定义在大于1的整数集合上的函数，令f(n)的值为不大于n的素数的个数，则：
limn→∞f(n)n/lnn=1
这个函数叫做素数分布函数，反映了素数的分布律。换言之，可以认为大于1的前n个正整数中，素数的个数大约是
n/lnn。
检测素数
所谓素数检测，就是给定任意一个大于1的整数，判断这个数是否素数。
因子检测法
最直观的素数检测算法就是因子检测法。说白了，就是从2到n1一个个拿来试，看能否整除n，如果有能整除的（找到一
个因子），则输出不是质数，否则则认为n为质数。当然，实际上不需要试探到n1，只要到n−−√就好了，原因如
下：
设n=a×b，且a、b均为n的非平凡约数，显然a>n−−√和b>n−−√不可能同时成立，因为同时成立时a*b就会大
于n，所以，如果n存在非平凡约数，则至少有一个小于等于n−−√，因此只要遍历到n−−√就可以了。
因子检测法的实现代码如下（python）：
1.defprime_test_factor(n):
2.ifn==1:
3.returnFalse
4.foriinrange(2,1+int(floor(sqrt(n)))):
5.ifn%i==0:
6.returnFalse
7.returnTrue
做几个测试：
1.printprime_test_factor(2)#True
2.printprime_test_factor(11)#True
3.printprime_test_factor(15)#False
4.printprime_test_factor(2147483647)#True
资源评论
NinjaPanda
- 粉丝: 30
- 资源: 231
最新资源
- 细胞的奇迹：吃出来的免疫力（美亚畅销书！作者的TED演讲播放量超300万次！《谷物大脑》作者、《三联生活周刊》推荐！吃下对的食物，改善你的... (Z-Library).azw3
- 智能手机产品拆解，使用mindmaster打开
- 11111111111111
- 统信系统ARM64依赖openssl-1.0.2版本的libssl.so.10和libcrypto.so.10文件
- 奥比中光python sdk
- 冯超楠17.py
- OCR识别-基于视觉注意力机制Attention实现的OCR识别算法-附项目源码-优质项目实战.zip
- Java 使用蒙特卡洛方法估算PI的近似值（源代码）
- main.cpp
- 电子木鱼小程序源码电子木鱼小程序源码
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
