 ## java.math Class BitSieve

```java.lang.Object
|
+--java.math.BitSieve
```

class BitSieve
extends Object

A simple bit sieve used for finding prime number candidates. Allows setting and clearing of bits in a storage array. The size of the sieve is assumed to be constant to reduce overhead. All the bits of a new bitSieve are zero, and bits are removed from it by setting them. To reduce storage space and increase efficiency, no even numbers are represented in the sieve (each bit in the sieve represents an odd number). The relationship between the index of a bit and the number it represents is given by N = offset + (2*index + 1); Where N is the integer represented by a bit in the sieve, offset is some even integer offset indicating where the sieve begins, and index is the index of a bit in the sieve array.

Since:
1.3
Version:
1.8, 06/11/02
Author:
Michael McCloskey
See Also:
`BigInteger`

 Field Summary `private  long[]` `bits`           Stores the bits in this bitSieve. `private  int` `length`           Length is how many bits this sieve holds. `private static BitSieve` `smallSieve`           A small sieve used to filter out multiples of small primes in a search sieve.

 Constructor Summary `private ` `BitSieve()`           Construct a "small sieve" with a base of 0. `(package private)` ```BitSieve(BigInteger base, int searchLen)```           Construct a bit sieve of searchLen bits used for finding prime number candidates.

 Method Summary `private static long` `bit(int bitIndex)`           Return a unit that masks the specified bit in its unit. `private  boolean` `get(int bitIndex)`           Get the value of the bit at the specified index. `(package private)  BigInteger` ```retrieve(BigInteger initValue, int certainty)```           Test probable primes in the sieve and return successful candidates. `private  void` `set(int bitIndex)`           Set the bit at the specified index. `private  int` ```sieveSearch(int limit, int start)```           This method returns the index of the first clear bit in the search array that occurs at or after start. `private  void` ```sieveSingle(int limit, int start, int step)```           Sieve a single set of multiples out of the sieve. `private static int` `unitIndex(int bitIndex)`           Given a bit index return unit index containing it.

 Methods inherited from class java.lang.Object `clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`

 Field Detail

### bits

`private long[] bits`
Stores the bits in this bitSieve.

### length

`private int length`
Length is how many bits this sieve holds.

### smallSieve

`private static BitSieve smallSieve`
A small sieve used to filter out multiples of small primes in a search sieve.

 Constructor Detail

### BitSieve

`private BitSieve()`
Construct a "small sieve" with a base of 0. This constructor is used internally to generate the set of "small primes" whose multiples are excluded from sieves generated by the main (package private) constructor, BitSieve(BigInteger base, int searchLen). The length of the sieve generated by this constructor was chosen for performance; it controls a tradeoff between how much time is spent constructing other sieves, and how much time is wasted testing composite candidates for primality. The length was chosen experimentally to yield good performance.

### BitSieve

```BitSieve(BigInteger base,
int searchLen)```
Construct a bit sieve of searchLen bits used for finding prime number candidates. The new sieve begins at the specified base, which must be even.

 Method Detail

### unitIndex

`private static int unitIndex(int bitIndex)`
Given a bit index return unit index containing it.

### bit

`private static long bit(int bitIndex)`
Return a unit that masks the specified bit in its unit.

### get

`private boolean get(int bitIndex)`
Get the value of the bit at the specified index.

### set

`private void set(int bitIndex)`
Set the bit at the specified index.

### sieveSearch

```private int sieveSearch(int limit,
int start)```
This method returns the index of the first clear bit in the search array that occurs at or after start. It will not search past the specified limit. It returns -1 if there is no such clear bit.

### sieveSingle

```private void sieveSingle(int limit,
int start,
int step)```
Sieve a single set of multiples out of the sieve. Begin to remove multiples of the specified step starting at the specified start index, up to the specified limit.

### retrieve

```BigInteger retrieve(BigInteger initValue,
int certainty)```
Test probable primes in the sieve and return successful candidates. comments? 