PROJECT EULER #69

Link to Project Euler problem 69

Euler's Totient function, φ(n) [sometimes called the phi function], is used to determine the number of numbers less than n which are relatively prime to n. For example, as 1, 2, 4, 5, 7, and 8, are all less than nine and relatively prime to nine, φ(9)=6.

n	Relatively Prime	φ(n)	n/φ(n)
2	1	1	2
3	1,2	2	1.5
4	1,3	2	2
5	1,2,3,4	4	1.25
6	1,5	2	3
7	1,2,3,4,5,6	6	1.1666...
8	1,3,5,7	4	2
9	1,2,4,5,7,8	6	1.5
10	1,3,7,9	4	2.5

It can be seen that n=6 produces a maximum n/φ(n) for n 10.

Find the value of n 1,000,000 for which n/φ(n) is a maximum.

Brute-forcing the totients up to a million would take hours (?) so I found a more elegant formula:

using System;
using System.Collections.Generic;

namespace project_euler
{
class Program
{
    private static List<int> primes = GeneratePrimes((int)Math.Sqrt(1000000));
    static void Main()
    {
        //Problem 69
        DateTime start = DateTime.Now;
        double max = 0;
        int number = 1;
        for (int i = 1000000; i >= 2; i--)
            if (i / Totient(i) > max)
            {
                max = i / Totient(i) > max ? i / Totient(i) : max;
                number = i;
            }
        Console.WriteLine(number);
        TimeSpan time = DateTime.Now - start;
        Console.WriteLine("This took {0}", time);
        Console.ReadKey();
    }

    public static double Totient(int n)
    {
        double totient = n;
        var primeFactorsOfN = new List<int>();
        foreach (int i in primes)
        {
            if (n % i == 0 && n != i) primeFactorsOfN.Add(i);
            if (i > Math.Sqrt(n)) break;
        }
        foreach (int i in primeFactorsOfN)
            totient *= 1 - 1 / (double)i;
        return totient;
    }

    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 primes = new List<int> { 2, 3 };
        for (int i = 5; i <= n; i += 2)
            if (IsPrime(i))
                primes.Add(i);
        return primes;
    }
}
}