PROJECT EULER #77

Link to Project Euler problem 77

It is possible to write ten as the sum of primes in exactly five different ways:

7 + 3
5 + 5
5 + 3 + 2
3 + 3 + 2 + 2
2 + 2 + 2 + 2 + 2

What is the first value which can be written as the sum of primes in over five thousand different ways?

A modification of the previous algorithm

using System;
using System.Collections.Generic;

namespace ProjectEuler
{
    class Program
    {
        static void Main()
        {
            //Problem 77
            DateTime start = DateTime.Now;
            var primes = GeneratePrimes(80);
            int maxNumber = 80,target=0,sum=0;
            int[,] a = new int[maxNumber + 1, maxNumber + 1];
            for (int i = 0; i < maxNumber + 1; i++)
            {
                a[i, 0] = 0;
                a[0, i] = 1;
            }
            int n = 2;
            while (sum < 5000)
            {
                    if (n%2 == 0) a[n, 1] = 1;
                    else a[n, 1] = 0;
                    for (int j = 2; j < primes.Count; j++)
                    {
                        int k = n - primes[j];
                        if (k < 0)
                            a[n, j] = a[n, j - 1];
                        else
                            a[n, j] = a[n, j - 1] + a[k, j];
                        if (a[n, j] > 5000)
                        {
                            target = n;
                            sum = a[n, j];
                            break;
                        }
                    }
                n++;
            }
            Console.WriteLine(sum + "  " +target);
            TimeSpan time = DateTime.Now - start;
            Console.WriteLine("This took {0}", time);
            Console.ReadKey();
        }
        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> { 0,2, 3 };
            for (int i = 5; i <= n; i += 2)
                if (IsPrime(i))
                    primeNumbers.Add(i);
            return primeNumbers;
        }
    }
}

PROJECT EULER #73

Link to Project Euler problem 73

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.
If we list the set of reduced proper fractions for d <= 8 in ascending order of size, we get:

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 3 fractions between 1/3 and 1/2.
How many fractions lie between 1/3 and 1/2 in the sorted set of reduced proper fractions for d <= 10,000?

Yet again a big thanks to my mentor: After trying to brute-force this by generating all the fractions using the a/b < c/d ...insert (a+c) /(b+d) if b+d = n, type of solution (I stopped the program after 40 mins) he suggested looking at this strategy (took 1.05 s):

using System;
using System.Collections.Generic;

namespace ProjectEuler
{
    class Program
    {
        static void Main()
        {
            //Problem 73
            DateTime start = DateTime.Now;
            int number =10000;
            var primeFactors = GeneratePrimeFactors(number);
            int max = 0,min=0,sum=0;
            for (int i = number; i > 3; i--)
            {
                int count = 0;
                max = (int) Math.Floor((decimal) i/2);
                min=(int)Math.Ceiling((decimal) i/3);
                for (int j = min; j <=max; j++)
                {
                    int test = primeFactors[i].Count;
                    foreach (int k in primeFactors[i])
                        if (j%k == 0)
                            test--;
                    if (test == primeFactors[i].Count)
                        count++;
                }
                sum += count;
            }
            Console.WriteLine(sum);
            Console.WriteLine();
            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>> {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 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 #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 #70

Link to Project Euler problem 70

Euler's Totient function, φ(n) [sometimes called the phi function], is used to determine the number of positive numbers less than or equal to 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.
The number 1 is considered to be relatively prime to every positive number, so φ(1)=1.

Interestingly, φ(87109)=79180, and it can be seen that 87109 is a permutation of 79180.

Find the value of n, 1 < n < src="http://projecteuler.net/index.php?section=problems&id=70" style="display: none;" alt="^(">⁷, for which φ(n) is a permutation of n and the ratio n/φ(n) produces a minimum.

Have to admit that I tried to brute-force this one and fell asleep on the couch. On awakening the answer lay there but the program would have happily run for some days (?) before completing. Armed with advice from the forum I learned that there are many ways to skin a totient...

Euler (from projecteuler.net) wrote:

Given n=p1e1p2e2...p1e1, φ(n)=n(1-1/p1)(1-1/p2)...(1-1/pk).

Now for n/φ(n) to be minimised, φ(n) must be as close to n as possible; that is, we want to maximise φ(n).

When evaluating φ(n), we note that each time we multiply by (1-1/pi), it gets smaller, so we need to minimise the number of distinct prime factors in n.

If n were prime, it would end in 1,3,7, or 9, and subtracting 1 only changes the last digit (to 0,2,6, or 8), so it could not be a permutation.

Hence n=p1*p2 and we only need to search through a list of known prime pairs.

In addition, φ(p1*p2)=p1*p2*(1-1/p1)(1-1/p2)=(p1-1)(p2-1), so we can compute φ(n) more efficiently.

using System;
using System.Collections.Generic;

namespace project_euler
{
class Program
{
  private static List<int> primes = GenerateRangeOfPrimes(1000,5000);

  static void Main()
  {
      //Problem 70
      DateTime start = DateTime.Now;
      decimal min = 100;
      int number = 1;

      for (int j = primes.Count - 1; j >= 0; j--)
          for (int k = j - 1; k >= 1; k--)
          {
              int i = primes[j]*primes[k];
              if (i < 10000000)
              {
                  int totient = (primes[j] - 1)*(primes[k] - 1);
                  if (IsPermutation(i, totient))
                      if ((decimal) i/totient < min)
                      {
                          min = (decimal) i/totient;
                          number = i;
                          Console.WriteLine(number + ": " + min + " p1: " + primes[k] + " p2: " + primes[j]);
                      }
              }
          }
      TimeSpan time = DateTime.Now - start;
      Console.WriteLine("This took {0}", time);
      Console.ReadKey();
  }

  private static bool IsPermutation(int m,int n)
  {
      char[] c = m.ToString().ToCharArray();
      char[] d = n.ToString().ToCharArray();
      Array.Sort(c);
      Array.Sort(d);
      string s = new string(c);
      string t = new string(d);
      if (s == t) return true;
      return false;
  }

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

  private static List<int> GenerateRangeOfPrimes(int m,int n)
  {
      var p = new List<int> { 2, 3 };
      for (int i = 5; i <= n; i += 2)
          if (IsPrime(i))
              p.Add(i);
      while (p[0] < m)
          p.Remove(p[0]);
      return p;
  }
}
}

PROJECT EULER #60

Link to Project Euler problem 60

The primes 3, 7, 109, and 673, are quite remarkable. By taking any two primes and concatenating them in any order the result will always be prime. For example, taking 7 and 109, both 7109 and 1097 are prime. The sum of these four primes, 792, represents the lowest sum for a set of four primes with this property.

Find the lowest sum for a set of five primes for which any two primes concatenate to produce another prime.

A more brute-force approach is probably not possible to achieve...but it runs in less than 8 seconds so I'm not complaining! I also took for granted that the first result would be the lowest sum.

using System;
using System.Collections.Generic;

namespace project_euler
{
class Program
{
  static void Main()
  {
      //Problem 60
      DateTime start = DateTime.Now;
      List<int> primes = GeneratePrimes(10000);
      int sum;
      bool finished = false;
      for (int i = 0; i < primes.Count-4; i++)
      {
          string s = primes[i].ToString();
          for (int j = i+1; j < primes.Count-3; j++)
          {
              string t = primes[j].ToString();
              if (IsPrime(int.Parse(s + t)) &&
                  IsPrime(int.Parse(t + s)))
              {
                  for (int k = j+1; k < primes.Count-2; k++)
                  {
                      string u = primes[k].ToString();
                      if (IsPrime(int.Parse(s + u)) &&
                          IsPrime(int.Parse(u + s)) &&
                          IsPrime(int.Parse(t + u)) &&
                          IsPrime(int.Parse(u + t)))
                      {
                          for (int l = k+1; l < primes.Count-1; l++)
                          {
                              string v = primes[l].ToString();
                              if (IsPrime(int.Parse(s + v))&&
                                  IsPrime(int.Parse(t + v))&&
                                  IsPrime(int.Parse(u + v))&&
                                  IsPrime(int.Parse(v + s))&&
                                  IsPrime(int.Parse(v + t))&&
                                  IsPrime(int.Parse(v + u)))
                              {
                                  for (int m = l+1; m < primes.Count; m++)
                                  {
                                      string w = primes[m].ToString();
                                      if (IsPrime(int.Parse(s + w))&&
                                          IsPrime(int.Parse(t + w))&&
                                          IsPrime(int.Parse(u + w))&&
                                          IsPrime(int.Parse(v + w))&&
                                          IsPrime(int.Parse(w + s))&&
                                          IsPrime(int.Parse(w + t))&&
                                          IsPrime(int.Parse(w + u))&&
                                          IsPrime(int.Parse(w + v)))
                                      {
                                          sum = primes[i] +
                                                primes[j] +
                                                primes[k] +
                                                primes[l] +
                                                primes[m];
                                          //min = sum < min ? sum : min;
                                          Console.WriteLine(sum);
                                          Console.WriteLine(primes[i] + " " +
                                                            primes[j] + " " +
                                                            primes[k] + " " +
                                                            primes[l] + " " +
                                                            primes[m]);
                                          finished = true;
                                          break;
                                      }
                                  }
                                  if (finished) break;
                              }
                          }
                          if (finished) break;
                      }
                  }
                  if (finished) break;
              }
           }
          if (finished) break;
      }
      TimeSpan time = DateTime.Now - start;
      Console.WriteLine("This took {0}", time);
      Console.ReadKey();
  }
  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;
  }
}
}

Triple-click for answer: 26033

PROJECT EULER #58

Link to Project Euler #58

Starting with 1 and spiralling anticlockwise in the following way, a square spiral with side length 7 is formed.

37 36 35 34 33 32 31
38 17 16 15 14 13 30
39 18 5 4 3 12 29
40 19 6 1 2 11 28
41 20 7 8 9 10 27
42 21 22 23 24 25 26
43 44 45 46 47 48 49

It is interesting to note that the odd squares lie along the bottom right diagonal, but what is more interesting is that 8 out of the 13 numbers lying along both diagonals are prime; that is, a ratio of 8/13 62%.

If one complete new layer is wrapped around the spiral above, a square spiral with side length 9 will be formed. If this process is continued, what is the side length of the square spiral for which the ratio of primes along both diagonals first falls below 10%?

for a n x n anticlockwise spiral, the corners are given by:
top right: n^2 - 3n + 3,
top left: n^2 - 2n + 2,
bottom left: n^2 - n + 1,
bottom right: n^2.

using System;
namespace project_euler
{
class Program
{
 static void Main()
 {
     //Problem 58
     DateTime start = DateTime.Now;
     int i = 1,n;
     double primeCount = 0, numberCount = 1;
     do
     {
         n = 2*i + 1;
         if (IsPrime(n*n - 3*n + 3))
             primeCount++;
         if (IsPrime(n*n - 2*n + 2))
             primeCount++;
         if (IsPrime(n*n - n + 1))
             primeCount++;
         numberCount += 4;
         i++;
     } while (primeCount/numberCount > 0.1);
     Console.WriteLine(n);
     TimeSpan time = DateTime.Now - start;
     Console.WriteLine("This took {0}", time);
     Console.ReadKey();
 }
 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;
 }
}
}

Triple-click for answer: 26241

PROJECT EULER #51

Link to Project Euler problem 51

By replacing the 1st digit of *57, it turns out that six of the possible values: 157, 257, 457, 557, 757, and 857, are all prime.
By replacing the 3rd and 4th digits of 56**3 with the same digit, this 5-digit number is the first example having seven primes, yielding the family: 56003, 56113, 56333, 56443, 56663, 56773, and 56993. Consequently 56003, being the first member of this family, is the smallest prime with this property.
Find the smallest prime which, by replacing part of the number (not necessarily adjacent digits) with the same digit, is part of an eight prime value family.

using System;
using System.Collections.Generic;

namespace ProjectEuler
{
    class Program
    {
        static void Main()
        {
            //Problem 51
            string number = "";
            int count = 0;
            List<int> primes = GeneratePrimes(1000000);
            while (primes[0] < 100000)
                primes.Remove(primes[0]);
            DateTime start = DateTime.Now;
            foreach (int i in primes)
            {
                string s = i.ToString();
                for (int j = 0; j < s.Length; j++)
                {
                    char d = s[j];
                    count = 0;
                    for (int k = 0; k < 10; k++)
                    {
                        string t = s.Replace(d, char.Parse(k.ToString()));
                        if (IsPrime(int.Parse(t)) && int.Parse(t) > 100000)
                            count++;
                    }
                    if (count > 7)
                    {
                        number = s;
                        break;
                    }
                }
                if (count > 7)
                    break;
            }
            Console.WriteLine("the number {0} creates an 8 prime family", number);
            TimeSpan time = DateTime.Now - start;
            Console.WriteLine("This took {0}", time);
            Console.ReadKey();
        }
        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;
        }
    }
}

Triple-click for answer: 121313

PROJECT EULER #50

Link to Project Euler problem 50

The prime 41, can be written as the sum of six consecutive primes:
41 = 2 + 3 + 5 + 7 + 11 + 13
This is the longest sum of consecutive primes that adds to a prime below one-hundred.
The longest sum of consecutive primes below one-thousand that adds to a prime, contains 21 terms, and is equal to 953.
Which prime, below one-million, can be written as the sum of the most consecutive primes?

using System;
using System.Collections.Generic;

namespace project_euler
{
   class Program
   {
       static void Main()
       {
           //Problem 50
           DateTime start = DateTime.Now;
           List<int> primes = GeneratePrimes(1000000);
           int max = 0, total = 0, initial = 0;
           for (int i = 0; i < 5; i++)
           {
               int sum = 0, number = 0;
               for (int j = i; j < primes.Count; j++)
               {
                   sum += primes[j];
                   if (sum > 1000000) break;
                   number++;
                   if (primes.Contains(sum))
                       if (number > total)
                       {
                           total = number;
                           max = sum;
                           initial = primes[i];                                                     
                       }
               }
           }
           Console.WriteLine("{0} steps from {1} give {2}", total, initial, max);
           TimeSpan time = DateTime.Now - start;
           Console.WriteLine("This took {0}", time);
           Console.ReadKey();
       }
       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;
       }
   }
}

PROJECT EULER #49

Link to Projrct Euler poblem 49


The arithmetic sequence, 1487, 4817, 8147, in which each of the terms increases by 3330, is unusual in two ways: (i) each of the three terms are prime, and, (ii) each of the 4-digit numbers are permutations of one another.
There are no arithmetic sequences made up of three 1-, 2-, or 3-digit primes, exhibiting this property, but there is one other 4-digit increasing sequence.
What 12-digit number do you form by concatenating the three terms in this sequence?

using System;
using System.Collections.Generic;

namespace project_euler
{
   class Program
   {
       static void Main()
       {
           //Problem 49
           DateTime start = DateTime.Now;
           List<int> primes = GeneratePrimes(10000);
           while (primes[0] < 1000)
               primes.Remove(primes[0]);
           for (int i = 0; i < primes.Count; i++)
           {
               char[] c = primes[i].ToString().ToCharArray();
               Array.Sort(c);
               string s = new string(c);
               for (int j = i + 1; j < primes.Count; j++)
               {
                   char[] d = primes[j].ToString().ToCharArray();
                   Array.Sort(d);
                   string t = new string(d);
                   if (s == t)
                       if (primes.Contains(primes[i] + 2 * (primes[j] - primes[i])))
                       {
                           int third = primes[i] + 2 * (primes[j] - primes[i]);
                           char[] e = third.ToString().ToCharArray();
                           Array.Sort(e);
                           string u = new string(e);
                           if (u == t && u != "1478")
                           {
                               string result = primes[i].ToString() + primes[j] + third;
                               Console.WriteLine(result);
                           }
                       }
               }
           }
           TimeSpan time = DateTime.Now - start;
           Console.WriteLine("This took {0}", time);
           Console.ReadKey();
       }
       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;
       }
   }
}

PROJECT EULER #47

Link to Project Euler problem 47

The first two consecutive numbers to have two distinct prime factors are:
14 = 2 x 7
15 = 3 x 5
The first three consecutive numbers to have three distinct prime factors are:
644 = 2² x 7 x 23
645 = 3 x 5 x 43
646 = 2 x 17 x 19.
Find the first four consecutive integers to have four distinct primes factors. What is the first of these numbers?

Took me some time to work this one out. The hard work is done by the method distinctPrimeFactors which divides the number by the smallest prime factor, then checks to see if it can divide it again by this number. It increments only if the prime divisor is a new number.

using System;

namespace project_euler
{
   class Program
   {
       static void Main()
       {
           //Problem 47
           DateTime start = DateTime.Now;
           int startNumber = 644;
           while (true)
           {
               if (distinctPrimeFactors(startNumber)==4&&
                   distinctPrimeFactors(startNumber+1)==4&&
                   distinctPrimeFactors(startNumber+2)==4&&
                   distinctPrimeFactors(startNumber+3)==4)
               {
                   break;
               }
               startNumber++;
           }
           Console.WriteLine(startNumber);

           TimeSpan time = DateTime.Now - start;
           Console.WriteLine("This took {0}", time);
           Console.ReadKey();
       }
       public static int distinctPrimeFactors(int number)
       {
           int numFactors = 0;
           int prime = 2;
           bool newPrime = true;
           while (!IsPrime(number))
               if (number%prime == 0)
               {
                   number /= prime;
                   if (newPrime)
                       numFactors++;
                   newPrime = false;
               }
               else
               {
                   do
                       prime++; while (!IsPrime(prime));
                   newPrime = true;
               }
           numFactors++;
           return numFactors;
       }
       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;
       }
   }
}

PROJECT EULER #41

Link to Project Euler problem 41

We shall say that an n-digit number is pandigital if it makes use of all the digits 1 to n exactly once. For example, 2143 is a 4-digit pandigital and is also prime.

What is the largest n-digit pandigital prime that exists?

I can rule out 9 and 8 digit pandigitals because the sum of the digits is divisible by 9 which means they are not prime

using System;

namespace project_euler
{
class Program
{
   static void Main()
   {
       //Problem 41
       DateTime start = DateTime.Now;
       string test = "1234567";
       int max = 0;
       for (int i = 3; i < 7654321; i += 2)
       {
           string s = i.ToString();
           if (!s.Contains("0")||!s.EndsWith("5"))
           {
               char[] c = s.ToCharArray();
               Array.Sort(c);
               string t = new string(c);
               if (t == test.Substring(0, t.Length))
                   if (IsPrime(int.Parse(s)))
                       max = int.Parse(s) > max
                                 ? int.Parse(s)
                                 : max;
           }
       }
       Console.WriteLine(max);
       TimeSpan time = DateTime.Now - start;
       Console.WriteLine("This took {0}", time);
       Console.ReadKey();
   }
   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;
   }
}
}

PROJECT EULER #37

Link to Project Euler problem 37

The number 3797 has an interesting property. Being prime itself, it is possible to continuously remove digits from left to right, and remain prime at each stage: 3797, 797, 97, and 7. Similarly we can work from right to left: 3797, 379, 37, and 3.

Find the sum of the only eleven primes that are both truncatable from left to right and right to left.

NOTE: 2, 3, 5, and 7 are not considered to be truncatable primes.

using System;

namespace project_euler
{
class Program
{
    static void Main()
    {
        //Problem 37
        DateTime start = DateTime.Now;
        int sum = 0;
        for (int i = 9; i < 1000000; i+=2)
        {
            string s = i.ToString();
            if (!s.Contains("0") || !s.Contains("4") || !s.Contains("6") || !s.Contains("8"))
            {
                bool test = true;
                for (int j = 0; j < s.Length; j++)
                    if (!IsPrime(int.Parse(s.Substring(j, s.Length - j))) || !IsPrime(int.Parse(s.Substring(0, j + 1))))
                        test = false;
                if (test)
                    sum += i;
            }
        }
        Console.WriteLine(sum);
        TimeSpan time = DateTime.Now - start;
        Console.WriteLine("This took {0}", time);
        Console.ReadKey();
    }
    //test if prime
    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;
    }
}
}

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