import java.util.ArrayList;

public class Main {
    static int N = 10000;
    static int[] sieve;
    static ArrayList<Integer> primes;
    public static void main(String args[]) {
        long start = System.nanoTime();
        fillSieve();
        long end = System.nanoTime();
        System.out.println("OLD : " + primes.size() + " , time : "  + (end-start)/1000000.0);

        start = System.nanoTime();
        fillSieve2();
        end = System.nanoTime();
        System.out.println("NEW : " + primes.size() + " , time : "  + (end-start)/1000000.0);

    }

    static void fillSieve(){
        sieve = new int[N];
        primes = new ArrayList<Integer>();
        for(int i = 2; i < N; ++i){
            if(sieve[i] == 0){
                primes.add(i);
                for(int j = i*i; j < N; j += i){
                    sieve[j] = 1;
                }
            }
        }
    }

    static void fillSieve2(){
        sieve = new int[N];
        primes = new ArrayList<Integer>();
        for(int i = 2; i < N; ++i){
            if(sieve[i] == 0)
                primes.add(i);
            for(int j=0, si=primes.size(); j<si && i*primes.get(j)<N ; j++)
            {
                sieve[primes.get(j)*i] = 1;
                if(i%primes.get(j)==0) break;
            }
        }
    }
}