de.luschny.math.primes
Class PrimeSieve

java.lang.Object
de.luschny.math.primes.PrimeSieve
All Implemented Interfaces:
IPrimeSieve
public class PrimeSieve
extends java.lang.Object
implements IPrimeSieve


Sieve. 








Author:


Peter Luschny













Nested Class Summary




private 
static class


PrimeSieve.PrimeCollection 

          PrimeCollection.		




  





Field Summary




(package 
private) 
PositiveRange
primeRange


           		




(package 
private)  int[]
primes


           		




(package 
private) 
PositiveRange
sieveRange


           		




 






Constructor Summary




PrimeSieve(int 
n) 

          Constructs a prime sieve 
for the integer range [1,n].		




 






Method Summary




 IPrimeCollection
getCollection()


          The default collection of 
the full sieve.		




 IPrimeCollection
getCollection(int 
low, int high) 

          Gives the collection of the 
prime numbers in the given interval.		




 IPrimeCollection


getCollection(PositiveRange 
range) 

          Gives the collection of the 
prime numbers in the given range.		




 int
getNthPrime(int 
n) 

          Get the n-th prime number.		




private 
static int
getPiHighBound(long 
n) 

          Get a high bound for pi(n), 
the number of primes less or equal n.		




 de.luschny.math.arithmetic.Xint
getPrimorial(int 
low, int high) 

          Gives the product of the 
prime numbers in the given interval.		




 de.luschny.math.arithmetic.Xint


getPrimorial(PositiveRange 
range) 

          Gives the product of the 
prime numbers in the given range.		




 boolean
isPrime(int 
cand) 

          Checks if a given number 
is prime.		




private  
int
makePrimeList(int 
n) 

          Transforms the sieve of Eratosthenes 
into the sequence of prime numbers.		




private 
static void
sieveOfEratosthenes(boolean[] 
composite) 

          Prime number sieve, Eratosthenes 
(276-194 b. t.)		




 




Methods inherited from class java.lang.Object




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




  









Field Detail








primeRange


PositiveRange primeRange













primes


int[] primes













sieveRange


PositiveRange sieveRange















Constructor Detail







PrimeSieve


public PrimeSieve(int n)




Constructs a prime sieve for the integer range [1,n].





Parameters:


n - The upper bound of the range to be sieved.













Method Detail







getCollection


public IPrimeCollection getCollection()




The default collection of the full sieve.









Specified by:


getCollection 
in interface 
IPrimeSieve










Returns:


An collection of all prime numbers found by the sieve.











getCollection


public IPrimeCollection getCollection(int low,
                                      int high)




Gives the collection of the prime numbers in the given interval.









Specified by:


getCollection 
in interface 
IPrimeSieve










Parameters:


low - Lower bound of the collection.


high - Upper bound of the collection. 


Returns:


An collection of the prime numbers which are in the interval [low, high].











getCollection


public IPrimeCollection getCollection(PositiveRange range)




Gives the collection of the prime numbers in the given range.









Specified by:




getCollection in interface 
IPrimeSieve










Parameters:


range - The range of the collection. 


Returns:


The prime number collection.











getNthPrime


public int getNthPrime(int n)




Get the n-th prime number.









Specified by:


getNthPrime 
in interface 
IPrimeSieve










Parameters:


n - The index of the prime number. 


Returns:


The n-th prime number.











getPiHighBound


private static int getPiHighBound(long n)




Get a high bound for pi(n), the number of primes less or equal n.

















Parameters:


n - Bound of the primes. 


Returns:


A simple estimate of the number of primes <= n.











getPrimorial


public de.luschny.math.arithmetic.Xint getPrimorial(int low,
                                                    int high)




Gives the product of the prime numbers in the given interval.

















Parameters:


low - Lower bound of the collection.


high - Upper bound of the collection. 


Returns:


The product of the prime numbers which are in the interval [low, high].











getPrimorial


public de.luschny.math.arithmetic.Xint getPrimorial(PositiveRange range)




Gives the product of the prime numbers in the given range.

















Parameters:


range - The range of the collection. 


Returns:


The product of the prime numbers in the range.











isPrime


public boolean isPrime(int cand)




Checks if a given number is prime.









Specified by:


isPrime in 
interface 
IPrimeSieve










Parameters:


cand - The number to be checked. 


Returns:


True iff the given number is prime.











makePrimeList


private int makePrimeList(int n)




Transforms the sieve of Eratosthenes into the sequence of prime numbers.

















Parameters:


n - Upper bound of the sieve. 


Returns:


Number of primes found.











sieveOfEratosthenes


private static void sieveOfEratosthenes(boolean[] composite)




Prime number sieve, Eratosthenes (276-194 b. t.) This implementation considers 
only multiples of primes greater than 3, so the smallest value has to be mapped 
to 5. Note: There is no multiplication operation in this function.

















Parameters:


composite - After execution of the function this boolean 
array includes all composite numbers in [5,n] disregarding multiples of 
2 and 3.