import java.util.ArrayList; 
import java.util.LinkedList; 
/* 
 * PrimeNumberMillion.java 
 * 
 * Created on 2006년 10월 12일 (목), 오후 3:06 
 * 
 * To change this template, choose Tools | Template Manager 
 * and open the template in the editor. 
 */ 
 
/** 
 * 백만 : 260ms 
   천만 : 6720ms 
 * @author 강웅빈 
 */ 
public class PrimeNumberMillion { 
    private static int MAX; 
     
    public PrimeNumberMillion() { 
        MAX = 1000000; 
    } 
     
    public int getMax() { 
        return MAX; 
    } 
    public void setMax(int val) { 
        MAX = val; 
    } 
     
    public int[] getPrime() { 
         
        boolean list[] = new boolean[MAX+1]; 
        list[0] = true; 
        list[1] = true; 
         
        for(int number=2; number<MAX/2; number++) { 
            for(int cur=2; cur * number < MAX + 1; cur++) { 
                if(!list[cur*number]) { 
                    list[cur*number] = true; 
                } 
            } 
        } 
         
        int size = 0;; 
        for(int number=1; number<MAX+1; number++) { 
            if(!list[number]) { 
                size++; 
            } 
        } 
         
        int[] result = new int[size]; 
        int cur_pos = 0; 
        for(int number=1; number<MAX+1; number++) { 
            if(!list[number]) { 
                result[cur_pos] = number; 
                cur_pos++; 
            } 
        } 
        return result; 
         
         
    } 
     
    public static void main(String args[]) { 
        PrimeNumberMillion p = new PrimeNumberMillion(); 
        p.setMax(10000000); 
        long time_begin = System.currentTimeMillis(); 
        int[] result = p.getPrime(); 
        long time_end = System.currentTimeMillis(); 
        System.out.println("Time elapsed : "+ (time_end - time_begin) + "ms" ); 
         
        for(int i : result) { 
            //System.out.println(i); 
        } 
    } 
     
}