OpenJDK 27 · java.math.BitSieve · APIdia, the JavaDoc alternative

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.

Field Summary

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

Constructor Summary

Access	Constructor and Description
private	BitSieve() Construct a "small sieve" with a base of 0.
pack-priv	BitSieve(BigInteger base, int searchLen) Construct a bit sieve of searchLen bits used for finding prime number candidates.

Method Summary

Modifier and Type	Method and Description
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.
pack-priv BigInteger	retrieve(BigInteger initValue, int certainty, Random random) 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.

Inherited from java.lang.Object:: clone equals finalize getClass hashCode notify notifyAll toString wait wait wait

Field Detail

bits	back to summary
private final long[] bits Stores the bits in this bitSieve.

length	back to summary
private final int length Length is how many bits this sieve holds.

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

Constructor Detail

BitSieve	back to summary
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

back to summary

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	back to summary
pack-priv 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

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

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

retrieve	back to summary
pack-priv BigInteger retrieve(BigInteger initValue, int certainty, Random random) Test probable primes in the sieve and return successful candidates.

set	back to summary
private void set(int bitIndex) Set the bit at the specified index.

sieveSearch	back to summary
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	back to summary
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.