• 中文
    • English
  • 注册
  • 赞助本站

    • 支付宝
    • 微信
    • QQ

    感谢一直支持本站的所有人!

    • 查看作者
    • 如何用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
    • 4k
    • 请登录之后再进行评论

      登录
    • 做任务
    • 实时动态
    • 偏好设置
    • 返回顶部
    • 单栏布局 侧栏位置: