一. 知识点
-
质数(prime number)又称素数,有无限个。质数定义为在大于1的自然数中,除了1和它本身以外不再有其他因数,这样的数称为质数。
-
1不是素数
二. 代码实现
方法一
package tv.zhangjia.algorithms; public class Test { public boolean isPrime(int n) { if(n < 2) { return false; } for(int i = 2; i * i <= n; i++) { if(n % i == 0) { return false; } } return true; } public static void main(String[] args) { for(int i = 2; i <= 10; i++) { System.out.println(i + "是素数吗:" + new Test().isPrime(i)); } } } /*输出: 2是素数吗:true 3是素数吗:true 4是素数吗:false 5是素数吗:true 6是素数吗:false 7是素数吗:true 8是素数吗:false 9是素数吗:false 10是素数吗:false*/
方法二
package tv.zhangjia.algorithms; public class Test { public boolean isPrime(int n) { if (n < 2) { return false; } for (int i = 2; i < n; i++) { if (n % i == 0) { return false; } } return true; } public static void main(String[] args) { System.out.println("97" + new Test().isPrime(97)); System.out.println("for循环执行了:" + j + "次"); } } /*输出: 2是素数吗:true 3是素数吗:true 4是素数吗:false 5是素数吗:true 6是素数吗:false 7是素数吗:true 8是素数吗:false 9是素数吗:false 10是素数吗:false*/
三. 两个方法比较
虽然两个方法的结果是相同的,但是效率却极大的不同,我们可以通过查看for循环的执行次数,来比较两个方法的效率,这里我们以100以内的最大的素数97为例
首先看方法二:
//方法二: package tv.zhangjia.algorithms; public class Test { static int j = 0; public boolean isPrime(int n) { if (n < 2) { return false; } for (int i = 2; i < n; i++) { j++; if (n % i == 0) { return false; } } return true; } public static void main(String[] args) { System.out.println("97是素数吗:" + new Test().isPrime(97)); System.out.println("for循环执行了:" + j + "次"); } } /*97是素数吗:true for循环执行了:95次*/
再看方法一:
package tv.zhangjia.algorithms; public class Test { static int j = 0; public boolean isPrime(int n) { if (n < 2) { return false; } for (int i = 2; i * i <= n; i++) { j++; if (n % i == 0) { return false; } } return true; } public static void main(String[] args) { System.out.println("97是素数吗:" + new Test().isPrime(97)); System.out.println("for循环执行了:" + j + "次"); } } /*97是素数吗:true for循环执行了:8次*/
通过上面两个方法的比较我们可以看出,虽然两个方法的输出结果一致,但是方法一的效率是方法二的近十倍之高
四. 简单扩展
-
关于方法一,还是以97为例,i = 2开始,一直到i = 10的时候,退出for循环。为什么不用判断11 -95这些数字呢? 因为97除以10以后的任何数数字,都不是整数,就算我们假设这个结果是整数,也肯定比10小,然而比10小的数字,我们已经判断过了
-
关于方法一,其实只要把for循环中的i++改成i += 2,效率又会提示2倍,因为除了2以外,其他所有的偶数都不是素数,所以可以直接用i += 2来排除偶数
五. 参考资料
Algorithms 4th Edition
请登录之后再进行评论