Source code: mindbright/util/PrimeSieve.java
1 /******************************************************************************
2 *
3 * Copyright (c) 1998,99 by Mindbright Technology AB, Stockholm, Sweden.
4 * www.mindbright.se, info@mindbright.se
5 *
6 * This program is free software; you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License as published by
8 * the Free Software Foundation; either version 2 of the License, or
9 * (at your option) any later version.
10 *
11 * This program is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU General Public License for more details.
15 *
16 *****************************************************************************
17 * $Author: nallen $
18 * $Date: 2001/11/12 16:31:29 $
19 * $Name: $
20 *****************************************************************************/
21 package mindbright.util;
22
23 public final class PrimeSieve {
24
25 public final static byte[] bitCounts = {
26 0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,1,
27 2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,1,2,
28 2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,2,3,3,
29 4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,1,2,2,3,
30 2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,2,3,3,4,3,
31 4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,2,3,3,4,3,4,
32 4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,3,4,4,5,4,5,5,
33 6,4,5,5,6,5,6,6,7,4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8
34 };
35
36 int[] table;
37
38 public PrimeSieve(int x) {
39 if(x < 4)
40 x = 4;
41
42 int len = (x - 3) / (32 * 2);
43 table = new int[len];
44
45 int max = len * 32;
46 int stop = (int)java.lang.Math.sqrt((double)max) + 1;
47 for(int i = 0; i < stop ; i++) {
48 if((table[i / 32] & (1 << (i & (32 - 1)))) == 0) {
49 int k = 3 + i * 2;
50 for (int j = i + k; j < max; j += k) {
51 table[j / 32] |= (1 << (j & (32 - 1)));
52 }
53 }
54 }
55 }
56
57 public int availablePrimes() {
58 int i, bits, w, primes;
59 for(i = 0, primes = 2; i < table.length; i++) {
60 w = table[i];
61 for(bits = 0; w != 0; w >>>= 8) {
62 bits += (int)bitCounts[w & 0xff];
63 }
64 primes += (32 - bits);
65 }
66 return primes;
67 }
68
69 public int getNextPrime(int x) {
70 int p = ((x - 3) / 2) + 1;
71 switch (x) {
72 /* Trivial cases. */
73 case 0:
74 return 2;
75 case 1:
76 return 2;
77 case 2:
78 return 3;
79 /* Cases above 2 are handled with the table. */
80 default:
81 while(true) {
82 if((p / 32) >= table.length)
83 return 0;
84
85 if((table[p / 32] & (1 << (p & (32 - 1)))) == 0)
86 return p * 2 + 3;
87 p++;
88 }
89 }
90 }
91
92 /*
93 public static void main(String[] argv) {
94 PrimeSieve primes = new PrimeSieve(100);
95 int n = primes.availablePrimes();
96 System.out.println("num of primes: " + n - 1);
97 int p = 2;
98 int i;
99 for(i = 0; p != 0; i++) {
100 System.out.println(p);
101 p = primes.getNextPrime(p);
102 }
103 System.out.println("i = " + i);
104 }
105 */
106
107 }