标准版：大部分人都知道的比较快的方法：判断从2到sqrt(n)是否存在其约数，时间复杂度O(sqrt(n))
高配版：判断2之后，就可以判断从3到sqrt(n)之间的奇数了，无需再判断之间的偶数，时间复杂度O(sqrt(n)/2)
尊享版：
首先看一个关于质数分布的规律：大于等于5的质数一定和6的倍数相邻。例如5和7，11和13,17和19等等；
证明：令x≥1，将大于等于5的自然数表示如下：
··· 6x-1，6x，6x+1，6x+2，6x+3，6x+4，6x+5，6(x+1），6(x+1)+1 ···
可以看到，不和6的倍数相邻的数为6x+2，6x+3，6x+4，由于2(3x+1)，3(2x+1)，2(3x+2)，所以它们一定不是素数，再除去6x本身，显然，素数要出现只可能出现在6x的相邻两侧。因此在5到sqrt(n)中每6个数只判断2个，时间复杂度O(sqrt(n)/3)。
在高配版和尊享版中，都是一个剪枝的思想，高配版中裁剪了不必要的偶数，尊享版中裁剪了不和6的倍数相邻的数，虽然都没有降低时间复杂度的阶数，但都一定程度上加快了判断的速度。
在此给出尊享版C++代码：
#include
#include
using namespace std; int isPrime(int n) { //返回1表示判断为质数，0为非质数，在此没有进行输入异常检测 float n_sqrt; if(n==1) return 0; if(n==2 || n==3) return 1; if(n%6!=1 && n%6!=5) return 0; n_sqrt=floor(sqrt((float)n)); for(int i=5;i<=n_sqrt;i+=6) { if(n%(i)==0 | n%(i+2)==0) return 0; } return 1; } int main() { int flag; flag=isPrime(37); cout<
python 版代码参考：https://github.com/hichenway/UsefulCode/blob/master/isPrimeFunction.py
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/213343.html原文链接：https://javaforall.net
