Sieve Of Erasthothenes (Optimize Memory Version)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39

public class Sieve { private int prime[]; public boolean isPrime(int x) { if(x==2) return true; if(x<2 || x%2==0) return false; x>>=1; return (prime[x>>5] & (1<<(x&31))) == 0; } public Sieve(int n) { prime = new int[(n>>6)+1]; for(int i=3;i*i<=n;i+=2) { int hi = i>>1; if( (prime[hi>>5] & (1<<(hi&31))) == 0) { for(int j=i*i;j<=n;j+=i) if((j&1)!=0) { int hj = j>>1; prime[hj>>5] |= (1<<(hj&31)); } } } } public static void main(String []args) { long start = System.currentTimeMillis(); Sieve sieve = new Sieve(10000000); long finish = System.currentTimeMillis(); for(int i=0;i<100;i++) if(sieve.isPrime(i)) System.out.print(i + " "); System.out.println(""); System.out.println("Time : " + (finish-start)/1000.0 + " secs"); } }