blah~

Project Euler problem 7~

  1: class Program
  2:     {
  3:         static void Main(string[] args)
  4:         {
  5:             var sw = new Stopwatch();
  6: 
  7:             Console.WriteLine("The 10001st prime number");
  8:             sw.Start();
  9:             var sum1 = PrimeNumberInTerm(116684, 10001);
 10:             sw.Stop();
 11:             Console.WriteLine(string.Format("Sieve of Eratosthenes brute force way(tick:{0}): {1}", sw.ElapsedTicks, sum1));
 12: 
 13:             sw.Reset();
 14: 
 15:             Console.WriteLine("Press any key to exit");
 16:             Console.ReadKey();
 17:         }
 18: 
 19:         /// <summary>
 20:         ///  so basically i use Sieve of Eratosthenes to construct list of prime
 21:         ///  and using the Prime number theorem (http://en.wikipedia.org/wiki/Prime_Number_Theorem)
 22:         ///  x/ln(x) = 10001, solving x should give me a good ceiling.
 23:         ///  x came to be about 116684 (thank you, WolframAlpha)
 24:         ///  takes about 5k tick
 25:         ///  the 10001th prime is 104743
 26:         /// </summary>
 27:         /// <param name="n"></param>
 28:         /// <returns></returns>
 29:         static int PrimeNumberInTerm(long maxCeiling, int term)
 30:         {
 31:             var upper = maxCeiling;
 32:             var upperl = (int)Math.Sqrt(upper);
 33:             bool[] map = new bool[upper];
 34:             map[0] = true;
 35:             map[1] = true;
 36:             int count = 0;
 37: 
 38:             for (int l = 2; l < upperl; l++)
 39:             {
 40:                 if (map[l] == false)
 41:                 {
 42:                     for (long i = l * l; i < upper; i += l)
 43:                     {
 44:                         map[i] = true;
 45:                     }
 46:                 }
 47:             }
 48: 
 49:             for (int i = 0; i < upper; i++)
 50:             {
 51:                 if (map[i] == false)
 52:                     count++;
 53: 
 54:                 if (count == term)
 55:                     return i;
 56:             }
 57: 
 58:             return count;
 59:         }
 60:     }

Advertisements
This entry was posted in Programming. Bookmark the permalink.

Leave a Reply

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

WordPress.com Logo

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

Twitter picture

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

Facebook photo

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

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s