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
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
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.
Calculate Euler's Totient for every integer up to the given limit