Efficient multiple totient calculation in C#
For a certain problem in Project Euler, I needed a function to calculate the Totient of all numbers in [2..10^7]. Going over them one at a time and factorizing them would take too long, so I used a variant of the prime sieve to speed up the calculation. The code is not overly documented, but it should be relatively easy to grok once you understand how to calculate the Totient of a single number.
The time complexity is O(n log n).
/// <summary> /// Return an array of all totients in [0..n-1] /// </summary> /// <param name="n"></param> /// <returns></returns> public static long[] CalcTotients(long n) { long[] divisors = GetDivisors(n); long i; var phi = new long[n]; phi[1] = 1; for (i = 1; i < n; ++i) CalcTotient(i, phi, divisors); return phi; } /// <summary> /// For every integer, the result will contain its lowest divisor. /// </summary> /// <param name="n"></param> /// <returns></returns> private static long[] GetDivisors(long n) { var divisors = new long[n]; divisors[1] = 1; long i; for (i = 2; i < n; ++i) { if (divisors[i] != 0) continue; for (long j = i; j < n; j += i) divisors[j] = i; } return divisors; } private static long CalcTotient(long i, long[] phi, long[] divisors) { if (phi[i] != 0) return phi[i]; long div = divisors[i]; if (div == i) { phi[i] = i - 1; return phi[i]; } long lower = 1; int exp = 0; while ((i > 1) && (i % div == 0)) { i /= div; lower *= div; exp++; } if (i == 1) { phi[lower] = ((long)Math.Pow(div, exp - 1)) * (div-1); return phi[lower]; } phi[i*lower] = CalcTotient(i, phi, divisors) * CalcTotient(lower, phi, divisors); return phi[i*lower]; } |
