用“埃氏筛法”求2~100以内的素数。2~100以内的数,先去掉2的倍数,再去掉3的倍数,再去掉5的倍数,……依此类推,最后剩下的就是素数。
要求使用数组及增强的for语句。
提示:可以使用一个boolean类型的数组,所以“将某个数i去掉”,可以表示成a[i]=false。当然也可以使用其他方法。
请注意代码风格:类名、变量名的命名,以及必要注释等等;
评分标准: 使用了数组(3分); 使用增强的for语句(2分); 筛法求素数的功能正确(5分)。
定义0-100的数组,如果是质数,则该数组此位置为数组的编号,如果不是,则为0;
从小向大遍历数据,如果数据与之前判断好的素数可以相除尽,那么则为素数。(优化点在于:只判断与素数的除法,例如判断8是否为素数时,只需要判断8%2,不需要判断8%4,减小了时间复杂度)
public class homework2 { public static void main(String[] args){ //定义0-100的数组,如果是质数,则该数组此位置为数组的编号,如果不是,则为0 int[] nums = new int[101]; first_layer: for(int i=2; i<=100; i++){ for(int j=2; j < i; j++){ if(nums[j]!=0 && i%nums[j]==0){ continue first_layer; } } nums[i] = i; } // 输出筛选出来的素数 System.out.println("输出质数为:"); for(int num: nums){ if(num!=0){ System.out.println(num); } } } }