Answered by:
Find the 1,000,001st prime

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
Question
Answers

You can gain a little speed (>10% improvement) by using some published numbers. For example, if p(x) is the primecounting 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 Marked as answer by Leo Liu  MSFTModerator Wednesday, July 13, 2011 6:28 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[n1]);
Console.ReadKey();
}
}
}

Mike Marked as answer by Leo Liu  MSFTModerator Wednesday, July 13, 2011 6:27 AM
 Unmarked as answer by Link.fr Sunday, August 28, 2011 9:33 PM

You can gain a little speed (>10% improvement) by using some published numbers. For example, if p(x) is the primecounting 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 Marked as answer by Leo Liu  MSFTModerator Wednesday, July 13, 2011 6:28 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 Marked as answer by Leo Liu  MSFTModerator Wednesday, July 13, 2011 6:28 AM
 Unmarked as answer by Leo Liu  MSFTModerator Wednesday, July 13, 2011 6:28 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 thoughtstuff. He builds his castles in the air, from air, creating by exertion of the imagination."  Fred Brooks
 Marked as answer by Leo Liu  MSFTModerator Wednesday, July 13, 2011 6:28 AM
 Unmarked as answer by Link.fr Sunday, August 28, 2011 9:33 PM

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 Marked as answer by Leo Liu  MSFTModerator Wednesday, July 13, 2011 6:27 AM
 Unmarked as answer by Link.fr Sunday, August 28, 2011 9:32 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("yyyyMMddHHmmss.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("yyyyMMddHHmmss.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; } } }
 Marked as answer by Leo Liu  MSFTModerator Wednesday, July 13, 2011 6:28 AM
 Unmarked as answer by Link.fr Sunday, August 28, 2011 9:33 PM