edu.rit.hyb.prime

Class Sieve

java.lang.Object

edu.rit.hyb.prime.Sieve

public class Sieve
extends java.lang.Object

Class Sieve provides an object for finding prime numbers using the Sieve of Eratosthenes. A sieve is an array of Boolean flags, of a certain length, starting at a certain lower bound index. The flag at index p is true if p is a prime number and is false otherwise.

Constructor Summary

Constructors

Constructor and Description
Sieve(long lb, int len) Construct a new sieve object.

Method Summary

Modifier and Type	Method and Description
void	initialize() Initialize this sieve.
boolean	isPrime(long p) Determine if the given number is prime.
LongIterator	iterator() Obtain an iterator for the primes in this sieve.
long	lb() Get this sieve's lower bound index.
void	lb(long lb) Set this sieve's lower bound index.
void	len(int len) Set this sieve's length.
long	length() Get this sieve's length.
boolean	sieveOut(long p) Sieve out the given prime.
void	sieveOut(LongIterator iterator) Sieve out all primes returned by the given iterator.

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

Sieve

public Sieve(long lb,
             int len)

Construct a new sieve object.

Parameters:

lb - Lower bound index. Assumed to be a nonnegative even number.

len - Length. Assumed to be a nonnegative even number.

Method Detail

lb

public long lb()

Get this sieve's lower bound index.

Returns:

Lower bound index.

lb

public void lb(long lb)

Set this sieve's lower bound index.

Parameters:

lb - Lower bound index. Assumed to be a nonnegative even number.

length

public long length()

Get this sieve's length.

Returns:

Length.

len

public void len(int len)

Set this sieve's length.

Parameters:

len - Length. Assumed to be a nonnegative even number.

initialize

public void initialize()

Initialize this sieve. Afterwards, all even-numbered flags are false and all odd-numbered flags are true.

sieveOut

public boolean sieveOut(long p)

Sieve out the given prime. Afterwards, all flags corresponding to multiples of the given prime are false. It is assumed that p is an odd prime and that all multiples of smaller primes have previously been sieved out.

Parameters:

p - Prime to sieve out.

Returns:

True if sieving with further primes is required, false otherwise.

sieveOut

public void sieveOut(LongIterator iterator)
              throws java.io.IOException

Sieve out all primes returned by the given iterator. It is assumed that the iterator returns a sequence of the odd primes in ascending order (3, 5, 7, 11, . . .). Sieving continues until no further sieving is required or until the end of the iterator's sequence of primes, whichever comes first.

Parameters:

iterator - Iterator for a sequence of odd primes.

Throws:

java.io.IOException - Thrown if an I/O error occurred.

isPrime

public boolean isPrime(long p)

Determine if the given number is prime. It is assumed that all primes smaller than p have been sieved out.

Parameters:

p - Number to test.

Returns:

True if p is prime, false otherwise.

iterator

public LongIterator iterator()

Obtain an iterator for the primes in this sieve. The iterator returns a sequence of the numbers whose flags are true in this sieve.

Returns:

Iterator.