Math.Sieve.Phi

This is a sieve that calculates Euler's Totient, also know as Euler's Phi function, for every number up to a given limit. phi(n) is defined as the number of positive integers less than n that are relatively prime to n, i.e. gcd n x == 1. Given the prime factorization of a number, it can be calculated efficiently from the formulas:

 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

The second case says that phi is a multiplicative function. Since any multiplicative function can be calculated from the prime factorization, Factor can also be applied, however this variant avoids a great deal of integer division, and so is significantly faster for calculating phi 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.

Documentation

sieve :: (Show a, Integral a) => a -> PhiSieve

Calculate Euler's Totient for every integer up to the given limit

phi :: (Integral a, Integral b) => PhiSieve -> a -> b

Retrieves the totient from the sieve

isPrime :: Integral a => PhiSieve -> a -> Bool

Is the given number prime?

sieveBound :: Integral a => PhiSieve -> a

The upper limit of the sieve