100以内所有质数的输出

2021-10-27

字数统计: 909字 | 阅读时长: 3分

质数求解的基本思路及优化。

1.基本思路

 /*
 100以内的所有质数的输出
 质数：素数，只能被1和它本身整除的自然数。 -->从2开始，到这个数-1结束为止，都不能被这个数本身整除。
 */
public class Prime {
    public static void main(String[] args) {
    	// 标识i是否被j除尽，一旦除尽，修改其值
    	boolean isFlag = true;
    	  //遍历2-100 最小的质数是2
          for(int i=2;i<=100;i++) {
        	  //从2开始，到这个数-1结束为止，都不能被这个数本身整除。
        	  for(int j=2;j<i;j++) {
        		  //i%j==0判断出不是质数，但是题目条件是求质数
        		  //i%j!=0亦不能直接判断出结果，当内层循环走完才能判断结果
        		  if(i%j==0){ // i被j除尽
        			  isFlag = false;
        		  }
        	  }
        	  // 判断若是还是为真，那么本次循环是质数
        	  if(isFlag == true) {
        		 System.out.println(i);  
        	  }
        	  // 重要：上面只考虑了是质数的情况，还有不是质数的情况，故需要重置标识
        	  isFlag = true;
          }
    }
}

2.算法优化（一）

优化1：在内层循环判断条件中添加break;

/*
100以内的所有质数的输出
质数：素数，只能被1和它本身整除的自然数。 -->从2开始，到这个数-1结束为止，都不能被这个数本身整除。
*/
public class Prime {
    public static void main(String[] args) {
    	// 标识i是否被j除尽，一旦除尽，修改其值
    	boolean isFlag = true;
    	  //遍历2-100 最小的质数是2
          for(int i=2;i<=100;i++) {
        	  //从2开始，到这个数-1结束为止，都不能被这个数本身整除。
        	  for(int j=2;j<i;j++) {
        		  //i%j==0判断出不是质数，但是题目条件是求质数
        		  //i%j!=0亦不能直接判断出结果，当内层循环走完才能判断结果
        		  if(i%j==0){ // i被j除尽
        			  isFlag = false;
        			  //优化一：只对本身非质数的自然数有效
        			  break;
        		  }
        	  }
        	  // 判断若是还是为真，那么本次循环是质数
        	  if(isFlag == true) {
        		 System.out.println(i);  
        	  }
        	  // 重要：上面只考虑了是质数的情况，还有不是质数的情况，故需要重置标识
        	  isFlag = true;
          }
    }
}

3.算法优化（二）

优化2：j<=Math.sqrt(i);质数原理：两端只需要判断一次，注意此时是=，不是<

/*
 100以内的所有质数的输出
 质数：素数，只能被1和它本身整除的自然数。 -->从2开始，到这个数-1结束为止，都不能被这个数本身整除。
 */
public class Prime {
    public static void main(String[] args) {
    	// 标识i是否被j除尽，一旦除尽，修改其值
    	boolean isFlag = true;
    	  //遍历2-100 最小的质数是2
          for(int i=2;i<=100;i++) {
        	  //从2开始，到这个数-1结束为止，都不能被这个数本身整除。
        	  //优化2：j<=Math.sqrt(i);两端只需要判断一次，注意此时是=，不是<
        	  for(int j=2;j<=Math.sqrt(i);j++) {
        		  //i%j==0判断出不是质数，但是题目条件是求质数
        		  //i%j!=0亦不能直接判断出结果，当内层循环走完才能判断结果
        		  if(i%j==0){ // i被j除尽
        			  isFlag = false;
        			  //优化一：只对本身非质数的自然数有效
        			  break;
        		  }
        	  }
        	  // 判断若是还是为真，那么本次循环是质数
        	  if(isFlag == true) {
        		 System.out.println(i);  
        	  }
        	  // 重要：上面只考虑了是质数的情况，还有不是质数的情况，故需要重置标识
        	  isFlag = true;
          }
    }
}

本文作者： 树叶莎莎遮窗棂
发布时间： 2021-10-27
最后更新： 2025-04-29
本文标题： 100以内所有质数的输出
本文链接： http://sysszcl.github.io/ article/c151f5f7.html
版权声明： 本作品采用 CC BY-NC-SA 4.0 许可协议进行许可。转载请注明出处！