none
Find the 1,000,001st prime

    Question

  • Dear experts,

    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 1,000,001st prime number ?

    I have written the algorithm by using trial division, Do you have any idea on a faster algorithm ?

    using System;
    using System.Diagnostics;
    
    namespace Problem7
    {
      class Program
      {
        static void Main(string[] args)
        {
          Stopwatch sw = Stopwatch.StartNew();
          Int64 p = GetPrime(1000001);
          sw.Stop();
    
          Console.WriteLine(p);
          Console.WriteLine("Profiling : {0} ms", sw.ElapsedMilliseconds); // 16838 ms
    
          Console.ReadKey();
        }
    
        // Main function
        static int GetPrime(int limit)
        {
          int count = 1;
          int p = 1; 
    
          do
          {
            p += 2;
            if (IsPrime(p))
              count++;
          }
          while (count < limit);
    
          return p;
        }
    
        // Checks if a number is prime
        static bool IsPrime(Int64 p)
        {
          if (p == 1)
            return false;
          else if (p < 4)
            return true;
          else if (p % 2 == 0)
            return false;
          else if (p < 9)
            return true;
          else if (p % 3 == 0)
            return false;
          else
          {
            Int64 sqrt = (Int64)Math.Sqrt(p);
    
            int d = 5;
            while (d <= sqrt)
            {
              if (p % d == 0)
                return false;
    
              if (p % (d + 2) == 0)
                return false;
    
              d += 6;
            }
          }
    
          return true;
        }
      }
    }
    
    


    Kind regards,


    aelassas.free.fr
    Wednesday, July 06, 2011 10:58 PM

Answers

  • You can gain a little speed (>10% improvement) by using some published numbers.  For example, if p(x) is the prime-counting function, then p(10,000,000) = 664,579.  So you can start computing with 10,million and skip having to find the first 664 thousand prime numbers (savings of 10 million iterations).  p(x) for x=100,Million is over 5 million, so the your problem is bounded by 10million and 100million leaving somewhat less than 90million values to test to find the 1,000,001st prime.

    See http://en.wikipedia.org/wiki/Prime_number_theorem for the chart.

     


    Les Potter, Xalnix Corporation, Yet Another C# Blog
    Thursday, July 07, 2011 1:03 AM

All replies


  • Problem 7 on Project Euler, which I presume you are asking about, is to get the 10,001st prime, not the 1,000,001st.
     
    You can try this code below which I used in helping to solve problems there.  It may be better than what you have:
     
    namespace Utils
    {
     public static class PrimeFactors
     {
      public static bool IsPrime(long value)
      {
       return FindPrimeFactors(value).Count == 1;
      }
     
      public static List<long> FindPrimeFactors(long value)
      {
       List<long> result = new List<long>();
       long maxfactor = (long) Math.Ceiling(Math.Sqrt(value));
       long x = 2;
     
       if (value == 2) { result.Add(value); return result; }
     
       while (x <= maxfactor)
       {
        if (value % x == 0)
        {
         result.AddRange(FindPrimeFactors(x));
         result.AddRange(FindPrimeFactors(value / x));
         return result;
        }
        else ++x;
       }
     
       // if code gets here, the value is prime
       result.Add(value);
       return result;
      }
     }
    }
     
    Here is my console app for running problem 7:
     
    namespace Project0007
    {
     /// <summary>
     /// 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?
     /// </summary>
     class Program
     {
      static void Main(string[] args)
      {
       List<long> Primes = new List<long>() { 2 };
       int n = 10001;
     
       while (Primes.Count < n)
       {
        if (Primes.Count % 25 == 0)
         Console.WriteLine("Working, found {0}", Primes.Count);
     
        // find the next prime value after Primes [Primes.Count - 1]
        long val = Primes[Primes.Count - 1] + 1;
        while (!Utils.PrimeFactors.IsPrime(val))
         ++val;
        Primes.Add(val);
       }
     
       Console.WriteLine("Prime [{0}] = {1}", n, Primes[n-1]);
       Console.ReadKey();
      }
     }
    }

    --
    Mike
    Thursday, July 07, 2011 12:31 AM
  • You can gain a little speed (>10% improvement) by using some published numbers.  For example, if p(x) is the prime-counting function, then p(10,000,000) = 664,579.  So you can start computing with 10,million and skip having to find the first 664 thousand prime numbers (savings of 10 million iterations).  p(x) for x=100,Million is over 5 million, so the your problem is bounded by 10million and 100million leaving somewhat less than 90million values to test to find the 1,000,001st prime.

    See http://en.wikipedia.org/wiki/Prime_number_theorem for the chart.

     


    Les Potter, Xalnix Corporation, Yet Another C# Blog
    Thursday, July 07, 2011 1:03 AM
  • Hello Mike,

    Yes! it is the problem 7 of project euler. I have resolved it (of course 10001st prime) but I am thinking about the optimization of the algorithm I made, that's why I am testing it with a 1,000,001st prime.

    I have just run your code with the 1,000,001st prime. The result was found in 162,182ms. However, The algorithm that I made, found  the result in 16,838ms.

    xalnix, What you propose would an approach. What takes time in the algorithm is the looping. With the the prime number theorem we can save some loopings.

    Kind regards,
    aelassas.free.fr
    Thursday, July 07, 2011 8:43 AM
  • Hi,

    This algorithim will display the 1,000,001 prime number in less than 1ms!!! oh yeah!

     

                Stopwatch sw = Stopwatch.StartNew();

                Console.Out.WriteLine("15485867");

                sw.Stop();

                Console.WriteLine("Profiling : {0} ms", sw.ElapsedMilliseconds);
                Console.ReadKey();

     

    Looked the value up.

     


    "The programmer, like the poet, works only slightly removed from pure thought-stuff. He builds his castles in the air, from air, creating by exertion of the imagination." - Fred Brooks

    Thursday, July 07, 2011 10:22 AM
  • Hi

    This algorithm should be optimized

    GET 'number'
    2) IF number <= 1 THEN
    Error Invalid Input
    3) ELSE IF number%2 == 0 && number != 2 THEN (even number other than two)
    Not prime / divisible by 2
    4) ELSE IF number%3 == 0 && number != 3 THEN
    Not prime / divisible by 3
    5) ELSE IF number%5 == 0 && number != 5 THEN
    Not prime / divisible by 5
    6) ELSE IF number%7 == 0 && number != 7 THEN
    Not prime / divisible by 7
    7) ELSE
    - SET 'divisor' TO 11
    - WHILE( divisor <= ceil[ sqrt(number) ] )
    - IF number%divisor == 0 && number != divisor THEN
    - Not prime / divisible by 'divisor'
    - ELSE IF ceil[ sqrt(number) ] == divisor THEN
    - PRIME!!!
    - ELSE increment divisor by 1


    The complexity resides in the simplicity Follow me at: http://smartssolutions.blogspot.com
    Thursday, July 07, 2011 2:52 PM
  • Try this if you want if you dont wisht o care for the time! (but hey, its does work!) - I will see if I can optimize it!

     

    using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;
    
    namespace ConsoleApplication2
    {
      class Program
      {
        static void Main(string[] args)
        {
          long a = long.Parse(Console.ReadLine());
          Console.WriteLine(DateTime.Now.ToString("yyyyMMdd-HHmmss.fff"));
          long i = 1;
          long j = 1;
          for (; i <=a; i++)
          {
            j++;
            for (; ; j++)
            {
              if (Prime(j) == true)
              {
                break;
              }
            }
    
          }
          Console.WriteLine(j);
          Console.WriteLine(DateTime.Now.ToString("yyyyMMdd-HHmmss.fff"));
          Console.ReadLine();
        }
    
        static bool Prime(long num)
        {
          //int factor = 0;
          for (int i = 2; i < num; i++)
          {
            if (num % i == 0)
            {
              return false;
            }
          }
          return true;
        }
    
    
      }
    }
    
    

     

    Friday, July 08, 2011 12:15 AM