-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | Number Theoretic Sieves:  primes, factorization, and Euler's Totient
--   
--   This package includes the Sieve of O'Neill and two generalizations of
--   the Sieve of Eratosthenes. The Sieve of O'Neill is a fully incremental
--   primality sieve based on priority queues. The other two are array
--   based, and are not incremental. One sieves the smallest prime factor,
--   and is useful if you want to factor a large quantity of small numbers.
--   The other sieves Euler's Totient, which is the number of positive
--   integers relatively prime and less than a given number.
@package NumberSieves
@version 0.0


-- | This is a sieve that calculates Euler's Totient, also know as Euler's
--   Phi function, for every number up to a given limit. <tt>phi(n)</tt> is
--   defined as the number of positive integers less than <tt>n</tt> that
--   are relatively prime to <tt>n</tt>, i.e. <tt>gcd n x == 1</tt>. Given
--   the prime factorization of a number, it can be calculated efficiently
--   from the formulas:
--   
--   <pre>
--   phi (p ^ k) = (p-1)*p^(k-1)    if p is prime
--   phi (x * y) = phi x * phi y    if x and y are relatively prime
--   </pre>
--   
--   The second case says that <tt>phi</tt> is a <i>multiplicative</i>
--   function. Since any multiplicative function can be calculated from the
--   prime factorization, <tt>NumberTheory.Sieve.Factor</tt> can also be
--   applied, however this variant avoids a great deal of integer division,
--   and so is significantly faster for calculating <tt>phi</tt> for large
--   quantities of different values.
--   
--   This sieve does not represent even numbers directly, and the maximum
--   number that can currently be sieved is 2^32. This means that the sieve
--   requires two bytes per number sieved on average, and thus sieving up
--   to 2^32 requires 8 GB of storage.
module NumberTheory.Sieve.Phi

-- | Calculate Euler's Totient for every integer up to the given limit
sieve :: (Integral a) => a -> PhiSieve

-- | Retrieves the totient from the sieve
phi :: (Integral a, Integral b) => PhiSieve -> a -> b

-- | Is the given number prime?
isPrime :: (Integral a) => PhiSieve -> a -> Bool

-- | The upper limit of the sieve
sieveBound :: (Integral a) => PhiSieve -> a
instance Ord PhiSieve
instance Eq PhiSieve
instance Show PhiSieve


-- | This is an array-based generalization of the Sieve of Eratosthenes
--   that associates a prime divisor to each number in the sieve. This is
--   useful if you want to factor a large quantity of small numbers
--   
--   This code contains two simple optimizations: even numbers are not
--   represented in the array, reducing both time and space by 50%.
--   Secondly, the smallest prime divisor is sieved, and the prime numbers
--   are represented by <a>0</a> in the array instead of themselves. This
--   allows the divisors to be stored in half the number of bits, reducing
--   space consumption by another 50%.
--   
--   Currently, this sieve is limited to numbers less than 2^32, and
--   consumes one byte per number in the sieve on average. Thus if you want
--   to find the smallest divisor of every number up to 2^32, you will need
--   4 GB of storage.
module NumberTheory.Sieve.Factor
data FactorSieve

-- | Returns the smallest prime divisor of a given number in the sieve.
findFactor :: (Integral a) => FactorSieve -> a -> a

-- | Returns the upper limit of a sieve.
sieveBound :: (Integral a) => FactorSieve -> a

-- | Is a number prime?
isPrime :: (Integral a) => FactorSieve -> a -> Bool

-- | Factors a number completely using a sieve, e.g.
--   
--   <pre>
--   factor (sieve 1000) 360 == [(2,3),(3,2),(5,1)]
--   </pre>
factor :: (Integral a) => FactorSieve -> a -> [(a, a)]

-- | Finds the smallest prime divisor of every number up to a given limit.
sieve :: (Integral a) => a -> FactorSieve
instance Ord FactorSieve
instance Eq FactorSieve
instance Show FactorSieve


-- | Incremental primality sieve based on priority queues, described in the
--   paper <i>The Genuine Sieve of Eratosthenes</i> by Melissa O'Neill,
--   <i>Journal of Functional Programming</i>, 19(1), pp95-106, Jan 2009.
--   
--   <a>http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf</a>
--   
--   Code is unchanged, other than packaging, from that written by Melissa
--   O'Neill. This version contains optimizations not described in the
--   paper, primarily improving memory consumption.
--   
--   <a>http://www.cs.hmc.edu/~oneill/code/haskell-primes.zip</a>
module NumberTheory.Sieve.ONeill

-- | An infinite stream of primes
primes :: (Integral a) => [a]

-- | The first argument specifies which number to start at, the second
--   argument is a wheel of deltas for skipping composites. For example,
--   <tt>primes</tt> could be defined as
--   
--   <pre>
--   2 : 3 : sieve 5 (cycle [2,4])
--   </pre>
sieve :: (Integral a) => a -> [a] -> [a]

-- | An infinite stream of primes
calcPrimes :: (Integral a) => () -> [a]

-- | Returns the first <tt>n</tt> primes
primesToNth :: (Integral a) => Int -> [a]

-- | Returns primes up to some limit
primesToLimit :: (Integral a) => a -> [a]
instance (Eq k, Eq v) => Eq (PriorityQ k v)
instance (Ord k, Ord v) => Ord (PriorityQ k v)
instance (Read k, Read v) => Read (PriorityQ k v)
instance (Show k, Show v) => Show (PriorityQ k v)