1 package 判断素数; 2  3 import java.util.ArrayList; 4  5 public class Shai { 6     public static void main(String[] s){ 7         System.out.println(    findPrime(100)); 8     } 9     private static ArrayList<Integer> findPrime(int n) {10         //1,先为数组中的数赋值11         int[] num = new int[n+1];//为了将n个数都存入且不与角标冲突，数组大小为n+1，这样我们只使用从角标为1的数组12         for(int i=0;i<=n;i++)13             num[i]=i;14         //2,依次去除合数，即将合数置零15         int end = (int) Math.sqrt(n);16         for(int i=2;i<=end;){17             for(int j=i*2;j<=n;j+=i){//注意j从i*2开始18                 num[j]=0;19             }20             i=next(num,i);21         }22         //3,最后再遍历数组，将未被置零的数也就是素数放入list中，返回list23         ArrayList<Integer> sushu=new ArrayList<Integer>();24         for(int i=2;i<n;i++){25             if( num[i]!=0){26                 sushu.add(num[i]);27             }28         }29         return sushu;30     }31     //找出下一个未被置零的数32     private static int next(int[] aa,int i) {33         while(aa[++i]==0){    34         }35         return i;36     }37 }