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;
        }
    }
}

PROJECT EULER #10

Link to Project Euler problem 10

The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.
Find the sum of all the primes below two million.

Prime question no. 3. Use the sieve to generate them, then add them up. Simple.

using System;
using System.Collections.Generic;

namespace ProjectEuler
{
   class Program
   {
       static void Main(string[] args)
       {
           //Problem 10
           DateTime start = DateTime.Now;
           List<int> primes= new List<int>() { 2, 3 };
           long sum = 0;

           for (int i = 5; i < 2000000; i += 2)
           {
               primes.Add(i);
               foreach (int j in primes)
               {
                   if (i % j == 0 && i != j)
                   {
                       primes.Remove(i);
                       break;
                   }
               }
           }
           foreach (int k in primes)
           {
               sum += k;
           }
           TimeSpan time = DateTime.Now-start;
           Console.WriteLine("{0}\nThis took {1}", sum, time);
           Console.ReadKey();
       }
   }
}

PROJECT EULER #7

Link to Project Euler problem 7

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.
What is the 10001st prime number?

The second prime question. Again the Sieve of Eratosthenes makes the primes.

using System;
using System.Collections.Generic;

namespace ProjectEuler
{
   class Program
   {
       static void Main(string[] args)
       {
           //Problem 7
           DateTime start = DateTime.Now;
           List<int> primes = new List<int>() { 2, 3 };
           for (int i = 5; primes.Count < 10001; i += 2)
           {
               primes.Add(i);
               foreach (int j in primes)
               {
                   if (i % j == 0 && i != j)
                   {
                       primes.Remove(i);
                       break;
                   }
               }
           }
           TimeSpan time = DateTime.Now-start;
           Console.WriteLine("{0}\nThis took {1}",primes[10000] ,time);
           Console.ReadKey();
       }
   }
}

PROJECT EULER #3

Link to Project Euler problem 3

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

The first of the prime questions. I use the "Sieve of Eratostosthenes" to generate primes.

using System;
using System.Collections.Generic;

namespace ProjectEuler
{
   class Program
   {
       static void Main(string[] args)
       {
           //Problem 3
           List<int> primes = new List<int> {2, 3};
           long largeNumber = 600851475143;
           int largestFactor = 0;
           DateTime start = DateTime.Now;
           for (int i = 5; i < Math.Sqrt(largeNumber); i += 2)
           {
               if (i % 3 != 0)
               {
                   primes.Add(i);
                   foreach (int j in primes)
                   {
                       if (i % j == 0 && i != j)
                       {
                           primes.Remove(i);
                           break;
                       }
                   }
               }
           }
           foreach(int k in primes)
           {
               if (largeNumber % k == 0)
                   largestFactor = k;
           }
           TimeSpan time = DateTime.Now - start;
           Console.WriteLine("{0}\nThis took {1}", largestFactor,time);
           Console.ReadKey();
       }
   }
}