Weiss数据结构--练习2.20扩展(素数 厄拉多塞筛)

package cn.yjnull.datastrhomework;
/** * 编写一个程序来确定正整数N是否是素数 * @author Yjnull * */
public class DataStr2_20 {
    //普通方法：判断是否是奇数(或者2),然后判断是否能被3,5,7,...,根号n 整除，不能则是素数
    //时间复杂度:O(根号N)
    public static boolean isPrime(int n){
        if(2==n) return true;
        if(n<=1||0==n%2){
            return false;
        }else{
            for(int i = 3;i<=Math.sqrt(n);i+=2){
                if(n%i==0){
                    return false;
                }
            }
            return true;
        }

    }

    //厄拉多塞筛：制作整数2到N的表，找出最小的未被删除的整数i，打印i，然后删除i，2i，3i,...
    //当i>根号N时结束。 
    //时间复杂度:O(NloglogN)
    public static void isEeatosthese(int n){
        int a[] = new int[n];
        int count=0;
        for (int i = 2; i < n; i++) //制作2到N的表
            a[i] = 1;
        for (int i = 2; i < Math.sqrt(n); i++) {
            if(1==a[i]) //找出最小的未被删除的i
                for (int j = i+i; j < n; j+=i) { //删除i,2i,3i,... 
                    a[j]=0;
                }
        }
        for (int i = 2; i < n; i++) { //打印结果
            if(1==a[i])
                //System.out.println(i+", ");
                count++;
        }
        System.out.println(count);
    }

    public static void main(String[] args) {
        int s=0;
        double time = System.currentTimeMillis();
        for (int i = 1; i <= 10000000; i++) {
            if(isPrime(i)){
                //System.out.print(i+", ");
                s++;
                //if(s%15==0&&s!=0)
                    //System.out.println();
            }
        }
        double time2 = System.currentTimeMillis();
        System.out.println(s+"\n"+(time2-time)+"ms");//s=664579(素数个数) time=4232.0ms

        double time3 = System.currentTimeMillis();
        isEeatosthese(10000000);
        double time4 = System.currentTimeMillis();
        System.out.println("\n"+(time4-time3)+"ms");//s=664579 time=175.0ms
    }

}