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

Math.Sieve.Phi

Description

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.

Synopsis

# Documentation

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