PROJECT EULER #72

Link to Project Euler problem 72

Consider the fraction, n/d, where n and d are positive integers. If n<d and HCF(n,d)=1, it is called a reduced proper fraction.

1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8

It can be seen that there are 21 elements in this set.
How many elements would be contained in the set of reduced proper fractions for d <= 1,000,000?

This was really beautiful. First I brute-forced it, using 35 minutes and then I searched the solution-forum for a better algorithm, without success. Then my mentor suggested this approach, which is so elegant that it deserves a name: The Sieve of Senehtsotare...16 seconds!

using System;
using System.Collections.Generic;

namespace ProjectEuler
{
    class Program
    {
        static void Main()
        {
            //Problem 72
            DateTime start = DateTime.Now;
            int number = 1000000;
            BigInt sum = new BigInt("1");
            var tots = GenerateTotients(number);
            foreach (KeyValuePair<int, int> pair in tots)
                sum += pair.Value;
            Console.WriteLine(sum-2);
            TimeSpan time = DateTime.Now - start;
            Console.WriteLine("This took {0}", time);
            Console.ReadKey();
        }
        public static List<List<int>> GeneratePrimeFactors(int n)
        {
            var primes = GeneratePrimes(n);
            var primeFactors = new List<List<int>>();
            primeFactors.Add(new List<int>{0});
            for (int i = 1; i <= n; i++)
                primeFactors.Add(new List<int>());
            if (n==1) return primeFactors;
            foreach (int i in primes)
                for (int j = i; j <= n; j += i)
                    primeFactors[j].Add(i);
            return primeFactors;
        }
        public static Dictionary<int, int> GenerateTotients(int n)
        {
            var totients = new Dictionary<int, int>{{0,0}};
            List<List<int>> primeFactors = GeneratePrimeFactors(n);
            for (int i = 1; i < primeFactors.Count; i++)
            {
                double totient = i;
                foreach (int j in primeFactors[i])
                    totient *= 1 - 1/(double) j;
                totients.Add(i,(int)totient);
            }
            return totients;
        }
        public static bool IsPrime(int n)
        {
            if (n < 2) return false;
            if (n == 2) return true;
            for (long i = 2; i <= Math.Sqrt(n); i++)
                if (n % i == 0) return false;
            return true;
        }
        public static List<int> GeneratePrimes(int n)
        {
            var primeNumbers = new List<int> { 2, 3 };
            for (int i = 5; i <= n; i += 2)
                if (IsPrime(i))
                    primeNumbers.Add(i);
            return primeNumbers;
        }
    }
}