Sunday, January 4, 2009

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");  
 }
 
}

5 comments:

  1. dear pak,
    in your blog, I see all about bit manipulation.
    why U interest with this in java?

    ReplyDelete
  2. He is an algorithms, if you want to know him,
    just click on Donate.. :D

    ReplyDelete
  3. Sorry.., i mean algorithmist.. :)

    ReplyDelete
  4. How about sieve that starts from some value a?

    ReplyDelete
  5. @linux:
    It's because I love Java and Algorithms :) .

    ReplyDelete