• 中文
    • English
  • 注册
  • 查看作者
  • 如何用Java判断任意一个数是否为素数

    一.  知识点

    • 质数(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

  • 0
  • 0
  • 0
  • 5.9k
  • 请登录之后再进行评论

    登录
    单栏布局 侧栏位置: