NumberSieves-0.1.2: Number Theoretic Sieves: primes, factorization, and Euler's Totient

Safe HaskellSafe-Infered



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.



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

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

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

Retrieves the totient from the sieve

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

Is the given number prime?

sieveBound :: Integral a => PhiSieve -> aSource

The upper limit of the sieve