View Javadoc

1   package net.sf.jperfprobe;
2   
3   /**
4    * Created by IntelliJ IDEA.
5    * User: tel
6    * Date: Dec 19, 2008
7    * Time: 10:50:09 AM
8    * To change this template use File | Settings | File Templates.
9    */
10  public class SieveBits {
11  
12      static public void main(String args[]) {
13          int n;
14          if (args.length == 0) {
15              n = 100000000;
16          } else {
17              n = Integer.parseInt(args[0]);
18          }
19          int k = (n - 3) / 2;
20          // warm up
21          countPrimes(10000);
22          System.out.println("Counting primes up to " + (2 * k + 3) + '.');
23          long time = System.currentTimeMillis();
24          int count = countPrimes(n);
25          time = System.currentTimeMillis() - time;
26          System.out.println(count + " primes found.");
27          System.out.println(time + " millis needed");
28      }
29  
30      static int countPrimes(int lngt) {
31          int k = (lngt - 3) / 2;
32          BitSet prime = new BitSet(k);
33          sieve(prime);
34          int count = 1;
35          for (int i = 0; i < k; i++) {
36              if (prime.get(i)) {
37                  count++;
38              }
39          }
40          return count;
41      }
42  
43      static void sieve(BitSet prime) {
44          int k = prime.size();
45          int p;
46          int l;
47          for (int i = 0; i < k; i++) {
48              prime.set(i);
49          }
50          for (int i = 0; i < k; i++) {
51              if (prime.get(i)) {
52                  p = 2 * i + 3;
53                  l = (p * p - 3) / 2;
54                  if (l > k) {
55                      break;
56                  }
57                  for (int j = l; j < k; j += p) {
58                      prime.clear(j);
59                  }
60              }
61          }
62      }
63  
64  }