输入一个整数n，求小于这个整数的所有质数。

淡淡的烟草味﹌ 2022-05-20 05:59 238阅读 0赞

算法：定义一个长度为n的boolean数组，true表示是质数，false表示不是质数。初始化为true,之后从2开始循环。

步骤：

I、找到第一个值为true的下标i。

II、把所有的下标为i的倍数的值 置为false。

III、直到扫描完数组中的所有数值。

IV、最后遍历数组，如果下标i的值为true，则说明i为质数。

import java.util.Scanner;
    /**
     * 
     * @author LLJ
     *	打印比n小的质数
     */
    public class ZhiShu5_1 {
    	public static void main(String[] args) {
    		Scanner sc = new Scanner(System.in);
    		System.out.println("请输入一个整数n:");
    		int n = sc.nextInt();
    		boolean[] b = new boolean[n+1];//初始化一个数组(boolean类型)
    		
    		for(int i = 0;i < b.length;i++){//初始化，所有值都为true
    			b[i]=true;
    		}
    		for(int j = 2;j < b.length;j++){//进行b.length轮筛选
    			if(b[j]){//j为true，也就是b[j]为质数
    				//把j的倍数设为false（因为一个数如果是质数，那它的倍数一定不是质数）
    				for(int k = j*2;k < b.length;k+=j){
    					b[k]=false;
    				}
    			}else{//否则，重新循环
    				continue;
    			}
    		}
    		//遍历数组
    		for(int z = 2;z < b.length;z++){
    			if(b[z]){//如果b[z]为true,则输出质数z
    				System.out.print(z + "\t");
    //				System.out.print(b[z] + "\t");//测试，打印此元素是否是质数
    			}
    		}
    		
    	}
    }