【中国大学MOOC】java程序设计-week3-用“埃氏筛法”求2～100以内的素数

本文主要是介绍【中国大学MOOC】java程序设计-week3-用“埃氏筛法”求2～100以内的素数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1.题目

用“埃氏筛法”求2～100以内的素数。2～100以内的数，先去掉2的倍数，再去掉3的倍数，再去掉5的倍数，……依此类推，最后剩下的就是素数。

要求使用数组及增强的for语句。

提示：可以使用一个boolean类型的数组，所以“将某个数i去掉”，可以表示成a[i]=false。当然也可以使用其他方法。

请注意代码风格：类名、变量名的命名，以及必要注释等等；

评分标准：
使用了数组（3分）；
使用增强的for语句（2分）；
筛法求素数的功能正确（5分）。

2.题解

定义0-100的数组，如果是质数，则该数组此位置为数组的编号，如果不是，则为0；
从小向大遍历数据，如果数据与之前判断好的素数可以相除尽，那么则为素数。（优化点在于：只判断与素数的除法，例如判断8是否为素数时，只需要判断8%2，不需要判断8%4，减小了时间复杂度）

public class homework2 {public static void main(String[] args){//定义0-100的数组，如果是质数，则该数组此位置为数组的编号，如果不是，则为0int[] 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);}}}
}