Euler Problems 41-60

Posted on by

Euler Problem 41:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace EulerProblem41
{
    class Program
    {
        static int counter;
        static void print(int[] v, int n)
        {
            if (counter < 1000000)
                return;
            foreach (int c in v)
                Console.Write(c.ToString());
            Console.WriteLine("");
        }
        static void Main(string[] args)
        {
            int[] v = new int[] { 9, 8, 7, 6, 5, 4, 3, 2, 1 };
            for (int i = 9; i > 0; i--)
            {
                for (int j = 0; j < 9; j++)
                {
                    int[] v1 = v.Skip(j).Take(i).ToArray();
                    permute(v1, 0, v1.Length);
                }
            }
        }
        static bool IsPrime(long n)
        {
            for (int i = 2; i < n; i++)
                if (n % i == 0)
                    return false;
            return true;
        }
        static void permute(int[] v, int start, int n)
        {
            if (start == n - 1)
            {
                counter++;
                string numm = "";
                for (int i = 0; i < v.Length; i++)
                    numm += v[i].ToString();
                if (IsPrime(int.Parse(numm)))
                {
                    Console.WriteLine(numm);
                    Console.Read();
                    return;

                }
            }
            else
            {
                for (int i = start; i < n; i++)
                {
                    int tmp = v[i];

                    v[i] = v[start];
                    v[start] = tmp;
                    permute(v, start + 1, n);
                    v[start] = v[i];
                    v[i] = tmp;
                }
            }

        }
    }
}

Euler Problem 42:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace EulerProblem42
{
    class Program
    {
        static void Main(string[] args)
        {
            //Triangle number generation
            List triengleNumbers = new List();
            for (int i = 1; i <= 26; i++)
                triengleNumbers.Add(TriangleNumber(i));

            //English letters
            var letters = new List { 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z' };
            //
            int triangleWords = 0;
            string[] strWords = System.IO.File.ReadAllText("words.txt").Split(new char[] { ',', '\"' }, StringSplitOptions.RemoveEmptyEntries);
            foreach (var word in strWords)
            {
                int sumWord = 0;
                for (int i = 0; i < word.Length; i++)
                    sumWord += letters.IndexOf(word[i]) + 1;
                if (triengleNumbers.Contains(sumWord))
                    triangleWords++;

            }

            Console.WriteLine(triangleWords);
            Console.Read();
        }

        static int TriangleNumber(int n)
        {
            return n * (n + 1) / 2;
        }
    }
}

Euler Problem 43:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace EulerProblem43
{
    class Program
    {
        static long sum = 0;
        static void Main(string[] args)
        {
            int[] v = new int[] { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
            permute(v, 0, 10);

            Console.WriteLine(sum);
            Console.Read();

        }
        static void permute(int[] v, int start, int n)
        {
            if (start == n - 1)
            {

                string numm = "";
                for (int i = 0; i < v.Length; i++)
                    numm += v[i].ToString();

                if (int.Parse(numm.Substring(1, 3)) % 2 == 0)
                {
                    if (int.Parse(numm.Substring(2, 3)) % 3 == 0)
                    {
                        if (int.Parse(numm.Substring(3, 3)) % 5 == 0)
                        {
                            if (int.Parse(numm.Substring(4, 3)) % 7 == 0)
                            {
                                if (int.Parse(numm.Substring(5, 3)) % 11 == 0)
                                {
                                    if (int.Parse(numm.Substring(6, 3)) % 13 == 0)
                                    {
                                        int nn = int.Parse(numm.Substring(7, 3));
                                        if (nn % 17 == 0)
                                        {
                                            sum += long.Parse(numm);
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
            else
            {
                for (int i = start; i < n; i++)
                {
                    int tmp = v[i];

                    v[i] = v[start];
                    v[start] = tmp;
                    permute(v, start + 1, n);
                    v[start] = v[i];
                    v[i] = tmp;
                }
            }

        }
    }
}

Euler Problem 44:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace EulerProblem44
{
    class Program
    {
        static void Main(string[] args)
        {
            long D = int.MaxValue;
            long numberofTerms = 5000;
            //for (long i = 1; i < 1000; i++)
            //Parallel implementation
            Parallel.For(1, numberofTerms, (i) =>
            {
                long pn = PentagonalNumber(i);
                for (long j = 1; j < i; j++)
                {
                    long pn2 = PentagonalNumber(j);
                    if (IsPentagonal(pn + pn2))
                    {
                        long dif = Math.Abs(pn - pn2);
                        if (IsPentagonal(dif))
                        {
                            if (dif < D)
                                System.Threading.Interlocked.Exchange(ref D, dif);
                        }
                    }
                }
            }
            );

            Console.WriteLine(D);
            Console.Read();
        }

        static long PentagonalNumber(long n)
        {
            return n * (3 * n - 1) / 2;
        }
        static bool IsPentagonal(long p)
        {
            double numb = (1.0 + Math.Sqrt(1.0 + 24.0 * p)) / 6.0;
            double nn = Math.Floor(numb);
            return numb == nn;
        }
    }
}

Euler Problem 45:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace EulerProblem45
{
    class Program
    {
        static void Main(string[] args)
        {
            int P = 165;
            int H = 143;
            for (int i = 283; ; i++)
            {
                long T = TriangleNumb(i);
                for (int j = (i / 2) - 1; j < 2 * i / 3; j++)
                {
                    //  int hh=H+j;
                    //  int pp=P+j;
                    long pent = PentagonalNumb(j);
                    for (int k = (i / 2) - 1; k < 2 * i / 3; k++)
                    {
                        long hex = HexagonalNumb(k);
                        if (T == hex && T == pent)
                        {
                            if (T > 40755)
                            {
                                Console.WriteLine(T);
                                Console.Read();
                                Environment.Exit(0);
                            }

                        }
                        else
                        {
                            if (T < pent || T < hex)
                                break;
                        }
                    }
                }

            }
        }

        static long TriangleNumb(long n)
        {
            return n * (n + 1) / 2;

        }
        static long PentagonalNumb(long n)
        {
            return n * (3 * n - 1) / 2;

        }
        static long HexagonalNumb(long n)
        {
            return n * (2 * n - 1);

        }
    }
}

Euler Problem 46:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;

namespace EulerProblem46
{
    class Program
    {
        static void Main(string[] args)
        {
            long i;

            for (i = 3; ; i += 2)
            {
                if (IsPrime(i))
                    continue;

                long pr = GetPrime(i);
                double kvadratD = 0;
                long kvadrat = 0;

                while (pr > 1)
                {
                    long n1 = (i - pr) / 2;
                    kvadratD = Math.Sqrt(n1);
                    kvadrat = (int)Math.Sqrt(n1);
                    if (kvadratD == kvadrat)
                        break;
                    pr = GetPrime(pr);
                    Debug.Assert(pr != 25);
                }
                if (kvadrat != kvadratD)
                    break;
                Debug.Assert(2777 != i);
            }
            Console.WriteLine(i);
            Console.Read();
        }
        static long GetPrime(long n)
        {
            for (long i = n - 1; i > 0; i--)
            {
                if (i % 2 == 0)
                    continue;
                if (IsPrime(i))
                    return i;
            }
            return 2;
        }

        static bool IsPrime(long n)
        {
            for (int i = 2; i * i <= n; i++)
                if (n % i == 0)
                    return false;
            return true;

        }
    }
}

Euler Problem 47:

i = 1; While[True, lst = FactorInteger[i][[All, 1]];
 If[Length[lst] == 4 &&
   Length[FactorInteger[i + 1][[All, 1]]] == 4 &&
   Length[FactorInteger[i + 2][[All, 1]]] == 4 &&
   Length[FactorInteger[i + 3][[All, 1]]] == 4,
  Break[], i = i + 1]
 ]; i

Euler Problem 48:

IntegerDigits[Sum[i^i, {i, 1, 1000}], 10, 10]

Euler Problem 49:

Uz korištenje biblioteke za kombinatoriku rješenje se dobije za manje od 1 sec.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;
//codeproject.com/KB/recipes/Combinatorics.aspx
using Facet.Combinatorics;

namespace EulerProblem49
{
class Program
{
static List<int> lst = new List<int>();
static void Main(string[] args)
{
    int[] v = new int[] {0, 1, 2, 3, 4, 5, 6, 7, 8,9 };
    Combinations<int> comb = new Combinations<int>(v,4, GenerateOption.WithRepetition);
    int i=0;

    foreach (var kombinacija in comb)
    {
        int[] vv = new int[4];

        for (i = 0; i < kombinacija.Count(); i++)
            vv[i] = int.Parse(kombinacija.ElementAt(i).ToString());

        lst.Clear();
        permute(vv, 0, 4);

        if (lst.Count > 2)
        {

           Combinations<int> comb1 =
               new Combinations<int>(Enumerable.Range(0, lst.Count).ToList(),
                                    3, GenerateOption.WithoutRepetition);
           foreach (var indexi in comb1)
            {
                if (lst[indexi.ElementAt(0)] == lst[indexi.ElementAt(1)] ||
                    lst[indexi.ElementAt(1)] == lst[indexi.ElementAt(2)])
                    continue;
                if (Math.Abs(lst[indexi.ElementAt(0)] - lst[indexi.ElementAt(1)]) ==
                    Math.Abs(lst[indexi.ElementAt(1)] - lst[indexi.ElementAt(2)]) &&
                    Math.Abs(lst[indexi.ElementAt(0)] - lst[indexi.ElementAt(1)]) == 3330)
                {
                    if (lst[indexi.ElementAt(0)] != 1487)
                    {
                        Console.WriteLine("Solution fo EP49: {0}",
                            lst[indexi.ElementAt(0)].ToString() +
                            lst[indexi.ElementAt(1)].ToString() +
                            lst[indexi.ElementAt(2)].ToString());
                        break;
                    }
                }
            }
        }

    }
    Console.WriteLine("Press any key to continue...");
    Console.Read();
}
static bool IsPrime(int n)
{
    for(int i=2; i*i<=n; i++)
        if(n%i==0)
          return false;
    return true;

}
static void permute(int[] v, int start, int n)
{
    if (start == n - 1)
    {

        string numm = "";
        for (int i = 0; i < v.Length; i++)
            numm += v[i].ToString();

        int number = int.Parse(numm);
        if(number.ToString().Length==4)
        {

            if (IsPrime(number))
                lst.Add(number);
        }
    }
    else
    {
        for (int i = start; i < n; i++)
        {
            int tmp = v[i];
            v[i] = v[start];
            v[start] = tmp;
            permute(v, start + 1, n);
            v[start] = v[i];
            v[i] = tmp;
        }
    }

}
}
}

Euler Problem 50:

U ovom zadatku smo koristili ParallelFx da bi ubrzali rješenje. I sekvencijalno implementirano rješenje dobija se oko minute:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Threading;
namespace EulerProblem50
{
class Program
{

    static void Main(string[] args)
    {
        int primCounter = 0;
        int primeNumber = 0;
        //78499 prim brojeva do milion
        List<int> lst = new List<int>();
        for (int i = 2; i < 1000000; i++)
            if (IsPrime(i))
                lst.Add(i);

        Parallel.For(0, lst.Count, (i) =>
        {
            int localCounter = 2;
            int primeSum = lst[i];
            int subIndex = i + 1;

            while (primeSum < 1000000 && subIndex < lst.Count - 1)
            {
                if (IsPrime(primeSum))
                {
                    if (primCounter < localCounter)
                    {
                        Interlocked.Exchange(ref primCounter, localCounter);
                        Interlocked.Exchange(ref primeNumber, primeSum);
                    }
                }
                primeSum = primeSum + lst[subIndex];
                subIndex = subIndex + 1;
                localCounter = localCounter + 1;
            }

        });

        Console.WriteLine("EP50= {0}", primeNumber);
        Console.WriteLine("Press any key top continue...");
        Console.Read();
    }

    static bool IsPrime(int n)
    {
        for (int i = 2; i * i <= n; i++)
            if (n % i == 0)
                return false;
        return true;
    }
}
}

Euler Problem 51:

Euler Problem 52:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace EulerProblem52
{
    class Program
    {
        static void Main(string[] args)
        {
            for (int i = 1; ; i++)
            {
                int x = i;
                int x2 = i * 2;
                int x3 = i * 3;
                int x4 = i * 4;
                int x5 = i * 5;
                int x6 = i * 6;

                var sx = i.ToString().OrderBy(p => p).ToArray();

                var sx2 = (i * 2).ToString().OrderBy(p => p).ToArray();
                var sx3 = (i * 3).ToString().OrderBy(p => p).ToArray();
                var sx4 = (i * 4).ToString().OrderBy(p => p).ToArray();
                var sx5 = (i * 5).ToString().OrderBy(p => p).ToArray();
                var sx6 = (i * 6).ToString().OrderBy(p => p).ToArray();
                string s1 = ""; string s2 = ""; string s3 = ""; string s4 = ""; string s5 = ""; string s6 = "";
                if (sx.Length == sx2.Length)
                {
                    if (sx2.Length == sx3.Length)
                    {
                        if (sx3.Length == sx4.Length)
                        {
                            if (sx4.Length == sx5.Length)
                            {
                                if (sx5.Length == sx6.Length)
                                {
                                    for (int j = 0; j < sx6.Length; j++)
                                    {
                                        s1 += sx[j].ToString();
                                        s2 += sx2[j].ToString();
                                        s3 += sx3[j].ToString();
                                        s4 += sx4[j].ToString();
                                        s5 += sx5[j].ToString();
                                        s6 += sx6[j].ToString();

                                    }
                                    if (s1 == s2 && s2 == s3 & s3 == s4 && s4 == s5 && s5 == s6)
                                        Console.WriteLine(i);
                                }
                            }
                        }
                    }
                }

            }
            Console.WriteLine("Kraj");
            Console.Read();
        }
    }
}

Euler Problem 53:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Numerics;
class Program
{
    static void Main(string[] args)
    {
        int count = 0;
        for (int i = 1; i <= 100; i++)
        {
            for (int j = 1; j <= 100; j++)
            {
                if (Komb(i, j) > 1000000)
                    count++;
            }
        }
        Console.WriteLine(count);
        Console.Read();
    }

    static BigInteger Komb(int n, int r)
    {
        BigInteger fact = 1;
        BigInteger nrfact = 1;

        for (int i = r + 1; i <= n; i++)
            fact *= i;
        for (int j = 1; j <= (n - r); j++)
            nrfact *= j;

        return (fact / nrfact);
    }
}

Euler Problem 54:

Za rješenje ovog problema korišten algoritam za poker pronađen ovdje.

  static void Main(string[] args)
        {
            int[] deck = new int[52];
            init_deck( deck );

           string buffer=System.IO.File.ReadAllText("poker.txt");
           var djeljenje = buffer.Split(new char[] { '\n', '\r' }, StringSplitOptions.RemoveEmptyEntries);

           int firstWiner = 0;
            int c1,c2,c3,c4,c5;//karte
           for (int i = 0; i < djeljenje.Length; i++)
           {
               string [] karte=djeljenje[i].Split(' ');
               //Player 1
               var broj= karte[0][0].ToString();
               var boja = karte[0][1].ToString();
               c1= ProstiBrojIzKarte(broj) | (RankIzKarte(broj) << 8) | BrojIzBoje(boja) | (1 << (16+RankIzKarte(broj)));

               broj= karte[1][0].ToString();
               boja = karte[1][1].ToString();
               c2= ProstiBrojIzKarte(broj) | (RankIzKarte(broj) << 8) | BrojIzBoje(boja) | (1 << (16+RankIzKarte(broj)));

               broj= karte[2][0].ToString();
               boja = karte[2][1].ToString();
               c3= ProstiBrojIzKarte(broj) | (RankIzKarte(broj) << 8) | BrojIzBoje(boja) | (1 << (16+RankIzKarte(broj)));

               broj= karte[3][0].ToString();
               boja = karte[3][1].ToString();
               c4= ProstiBrojIzKarte(broj) | (RankIzKarte(broj) << 8) | BrojIzBoje(boja) | (1 << (16+RankIzKarte(broj)));

               broj= karte[4][0].ToString();
               boja = karte[4][1].ToString();
               c5= ProstiBrojIzKarte(broj) | (RankIzKarte(broj) << 8) | BrojIzBoje(boja) | (1 << (16+RankIzKarte(broj)));

               int play1=eval_5cards( c1,  c2,  c3,  c4,  c5);

               //Player 2
               broj= karte[5][0].ToString();
               boja = karte[5][1].ToString();
               c1= ProstiBrojIzKarte(broj) | (RankIzKarte(broj) << 8) | BrojIzBoje(boja) | (1 << (16+RankIzKarte(broj)));

               broj= karte[6][0].ToString();
               boja = karte[6][1].ToString();
               c2= ProstiBrojIzKarte(broj) | (RankIzKarte(broj) << 8) | BrojIzBoje(boja) | (1 << (16+RankIzKarte(broj)));

               broj= karte[7][0].ToString();
               boja = karte[7][1].ToString();
               c3= ProstiBrojIzKarte(broj) | (RankIzKarte(broj) << 8) | BrojIzBoje(boja) | (1 << (16+RankIzKarte(broj)));

               broj= karte[8][0].ToString();
               boja = karte[8][1].ToString();
               c4= ProstiBrojIzKarte(broj) | (RankIzKarte(broj) << 8) | BrojIzBoje(boja) | (1 << (16+RankIzKarte(broj)));

               broj= karte[9][0].ToString();
               boja = karte[9][1].ToString();
               c5= ProstiBrojIzKarte(broj) | (RankIzKarte(broj) << 8) | BrojIzBoje(boja) | (1 << (16+RankIzKarte(broj)));

               int play2=eval_5cards( c1,  c2,  c3,  c4,  c5);

               if(play1<play2)
                   firstWiner++;

           }
           Console.WriteLine(firstWiner);
           Console.WriteLine("Press any key to continue...");
           Console.Read();
        }
        static int ProstiBrojIzKarte(string s)
        {
            switch (s)
            {
                case "2":
                    return 2;
                case "3":
                    return 3;
                case "4":
                    return 5;
                case "5":
                    return 7;
                case "6":
                    return 11;
                case "7":
                    return 13;
                case "8":
                    return 17;
                case "9":
                    return 19;
                case "T":
                    return 23;
                case "J":
                    return 29;
                case "Q":
                    return 31;
                case "K":
                    return 37;
                case "A":
                    return 41;
                default:
                    return 0;
            }
        }
        static int RankIzKarte(string s)
        {
            switch (s)
            {
                case "2":
                    return 0;
                case "3":
                    return 1;
                case "4":
                    return 2;
                case "5":
                    return 3;
                case "6":
                    return 4;
                case "7":
                    return 5;
                case "8":
                    return 6;
                case "9":
                    return 7;
                case "T":
                    return 8;
                case "J":
                    return 9;
                case "Q":
                    return 10;
                case "K":
                    return 11;
                case "A":
                    return 12;
                default:
                    return 0;
            }
        }
        static int BrojIzBoje(string s)
        {
            switch (s)
            {
                case "H":
                    return 32768;
                case "C":
                    return 16384;
                case "S":
                    return 8192;
                case "D":
                    return 4096;
                default:
                    return 0;
            }
        }

Euler Problem 55:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;
using System.Numerics;

namespace EulerProblem55
{
    class Program
    {
        static void Main(string[] args)
        {
            int count = 0;
            for (int i = 1; i < 10000; i++)
            {
                BigInteger n = i;
                bool LichNumb = true;

                for (int k = 1; k < 50; k++)
                {
                    n = n + Reverse(n);

                    if (IsPalindrom(n.ToString()))
                    {
                        LichNumb = false;
                        break;
                    }

                }
                if (LichNumb)
                    count++;
            }

            Console.WriteLine(count);
            Console.Read();
        }

        static BigInteger Reverse(BigInteger n)
        {
            string rn = n.ToString();
            string ss = "";
            foreach (var c in rn.Reverse())
                ss += c;
            return BigInteger.Parse(ss);
        }
        static bool IsPalindrom(string n)
        {
            int lnl;
            if (n.Length % 2 != 0)
                lnl = 1 + n.Length / 2;
            else
                lnl = n.Length / 2;

            int ln = n.Length;
            for (int i = 0; i < ln / 2; i++)
                if (n[i] != n[ln - 1 - i])
                    return false;
            return true;
        }
    }
}

Euler Problem 56:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Numerics;

namespace EulerProblem56
{
    class Program
    {
        static void Main(string[] args)
        {
            var res = (from a in Enumerable.Range(1, 99)
                       from b in Enumerable.Range(1, 99)
                       select BigInteger.Pow(a, b).ToString());
            int maxSum = 0;
            foreach (var s in res)
            {
                int parcijalanSuma = 0;
                foreach (var ch in s)
                    parcijalanSuma += int.Parse(ch.ToString());

                if (parcijalanSuma > maxSum)
                    maxSum = parcijalanSuma;
            }

            Console.WriteLine(maxSum);
            Console.Read();

        }
    }
}

Euler Problem 57:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Numerics;

namespace EulerProblem57
{
    class Program
    {
        static void Main(string[] args)
        {

            BigInteger x = 3;
            BigInteger y = 2;
            int counter = 0;
            for (long i = 2; i <= 1000; i++)
            {
                BigInteger tempx = 2 * y + x;
                BigInteger tempy = x + y;

               x = tempx;
               y = tempy;

               if (tempx.ToString().Length > tempy.ToString().Length)
                   counter++;

            }
            Console.WriteLine(counter);
            Console.Read();
        }

    }
}

Euler Problem 58:

Moguće je vrlo brzo doći do izraza koji generiraju brojeve na glavnoj i sporednoj dijagonali matrične forme. Izrazi su sljedeći:

i^{2}-i+1 – brojevi sporedne dijagonale -gornjeg dijela
i^{2}-3i+3 – brojevi sporedne dijagonale -donjeg dijela
i^{2}-2i+2 – brojevi glavne dijagonale – gornjeg dijela

Brojevi glavne dijagonale donjeg dijela nam nisu interesantni jer su potpuni kvadrati, pa onda nisu prosti brojevi. Sad kada imamo generator brojeva potrebno je još samo provjeriti da li su ti brojevi prosti. Ako bi išli brute force, sigurno rješenje ne bi dobili za nekoliko sati, pa je potrebno implementirati pametni algoritam. U principu kada povećavamo rank matrice, većim dijelog provjeravamo da li su brojevi prosti koje smo prethodno provjeravali i samo za iteraciju više provjeravamo novi broj. S toga je potrebno jednom čekirani broj zapamtiti i koristiti ga kasnije. Algoritam je bazira na korištenju Directory kolekcije u kojem kao Key definišemo broj koji smo provjeravali da li je prost, a u bool varijablu pohranjujemo true ako je dati broj prost inače stavljamo false.  Na tom se i temelji cijela implementacija algoritma:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace EulerProblem58
{
    class Program
    {
        static Dictionary<int, bool> primes = new Dictionary<int, bool>();
        static void Main(string[] args)
        {
            int m = 7;
            int primeCount=0;
            int temp;

            while (true)
            {
                primeCount = 0;
                for (int i = 2;i<=m+1; i++)
                {
                    if (i % 2 == 0)
                    {
                        temp = i * i - i + 1;
                        if (temp <= m * m)
                        {
                            if (IsPrimeNumber(temp))
                                primeCount++;
                        }
                        temp = i * i - 3 * i + 3;
                        if (temp <= m * m)
                        {
                            if (IsPrimeNumber(temp))
                                primeCount++;
                        }
                    }
                    else
                    {
                        temp = i * i - 2 * i + 2;
                        if (IsPrimeNumber(temp))
                             primeCount++;
                    }
                }

                if (primeCount / (2.0 * m - 1.0) < 0.1)
                {
                    Console.WriteLine((primeCount / (2.0 * m - 1.0)).ToString());
                    Console.WriteLine(m);
                    break;
                }
                m+=2;
            }
            Console.WriteLine("Press any key to continue...");
            Console.ReadLine();
        }

        private static bool IsPrimeNumber(int n)
        {
            if (primes.ContainsKey(n))
                return primes[n];
            else
            {
                if (IsPrime(n))
                {
                    primes.Add(n, true);
                    return true;
                }
                else
                {
                    primes.Add(n, false);
                    return false;
                }

            }

        }

        static bool IsPrime(long n)
        {
            if (n < 2) return false;
            if (n % 2 == 0) return n == 2;
            if (n % 3 == 0) return n == 3;

            for (int p = 5; ; )
            {
                long q = n / p;
                if (q < p)
                    break;
                if (q * p == n)
                    return false;

                p += 2;
                q = n / p;
                if (q < p)
                    break;
                if (q * p == n)
                    return false;
                p += 4;
            }
            return true;
        }
    }
}
Advertisement

Leave a Reply

Fill in your details below or click an icon to log in:

Gravatar
WordPress.com Logo

You are commenting using your WordPress.com account. ( Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. ( Log Out /  Change )

Cancel

Connecting to %s