Portability | portable |
---|---|

Stability | experimental |

Maintainer | leon@melding-monads.com |

Safe Haskell | Safe-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.