素数算法
目录
定义
1 常规方法判断
2 最有效方法判断
3 测试
定义
约数只有1和本身的整数称为质数，或称素数。
1 常规方法判断
根据定义，因为质数除了1和本身之外没有其他约数，所以判断n是否为质数，根据定义直接判断从2到n-1是否存在n的约数即可。
Java代码如下：
/**
* 判断是否为素数/质数的常规方法
* 判断n是否为素数，根据定义直接判断从2到n-1是否存在n的约数即可
* @param num
* @return
*/
public static boolean isPrimeNormal(int num) {
for(int i=2; i<num; i++) {
if(num%i == 0) {
return false;
}
}
return true;
}
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两侧的数为6x+2，6x+3，6x+4，由于2(3x+1)，3(2x+1)，2(3x+2)，所以它们一定不是素数，再除去6x本身，显然，素数要出现只可能出现在6x的相邻两侧。
另外，我们知道，一个数若可以进行因数分解，那么分解时得到的两个数一定是一个小于等于sqrt(n)，一个大于等于sqrt(n)，据此，上述代码中并不需要遍历到n-1，遍历到sqrt(n)即可，因为若sqrt(n)左侧找不到约数，那么右侧也一定找不到约数。
Java代码如下：
/**
* 判断是否为素数/质数的最有效方法
* 1.小于5的2和3
* 2.大于等于5的素数一定和6的倍数相邻，例如5和7，11和13,17和19等等。
* @param num
* @return
*/
public static boolean isPrime(int num) {
//两个较小数另外处理
if(num==2 || num==3) {
return true;
}
//不在6的倍数两侧的一定不是素数
if(num%6!=1 && num%6!=5) {
return false;
}
int tmp = (int) Math.sqrt(num);//获取平方根
//在6的倍数两侧的也可能不是素数
for(int i=5; i<=tmp; i+=6) {
if(num%i==0 || num%(i+2)==0) {
return false;
}
}
return true;
}
下面来看下，这两个方法的性能测试：
public static void main(String[] args) {
int testNum = 1000000;
//常规方法测试
long start1 = Calendar.getInstance().getTimeInMillis();
for(int i=0; i<testNum; i++) {
isPrimeNormal(i);
}
long end1 = Calendar.getInstance().getTimeInMillis();
System.out.println("常规方法，消耗时长(ms):" + (end1 - start1));
//最有效方法测试
long start2 = Calendar.getInstance().getTimeInMillis();
for(int i=0; i<testNum; i++) {
isPrime(i);
}
long end2 = Calendar.getInstance().getTimeInMillis();
System.out.println("最有效方法，消耗时长(ms):" + (end2 - start2));
}
3 测试
测试结果如下：
最后，注明下此算法思想出自：https://blog.csdn.net/huang_miao_xin/article/details/51331710
相关阅读
遗传算法原理解析 遗传算法（GA）是一种元启发式自然选择的过程，属于进化算法（EA）大类。遗传算法通常是利用生物启发算子，如变异、交叉和
上一篇我们看了dsa的分类和简单的内存管理算法实现，这篇文档我们来看TLSF的实现，一种更加高级的内存管理算法；一、实现原理 基本的Se
作为AI产品经理必懂算法的第二篇，来了解一下支持向量机SVM算法，英文全称是“Support Vector Machine”。在机器学习中，SVM是监督学习
文章整理自阿里云栖视频 DIFF算法在执行时有三个维度，分别是Tree DIFF、Component DIFF和Element DIFF，执行时按顺序依次执行，它们
首先什么是遗传算法：一个非常好的理解遗传算法的例子 强烈推荐入门 遗传算法的手工模拟计算示例 为更好地理解遗传算法的运算过