**Problem:**

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6^(th) prime is 13.

What is the 10001^(st) prime number?

**My Original Brut Force Solution knowing nothing about primes SLOW:**

using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace Euler { class Problem7 : IProblemBase { //By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, //we can see that the 6^(th) prime is 13. //What is the 10001^(st) prime number? //The algorithm //1. Create a contiguous list of numbers from two to some highest number n. //2. Strike out from the list all multiples of two (4, 6, 8 etc.). //3. The list's next number that has not been struck out is a prime number. //4. Strike out from the list all multiples of the number you identified in the previous step. //5. Repeat steps 3 and 4 until you reach a number that is greater than the square root of n (the highest number in the list). //6. All the remaining numbers in the list are prime. public Problem7() { } public string GetAnswer() { int primeCount = 0; int result = 0; for(int i=2;i>0;i++) //loop forever starting at 1 { int matchCount = 0; for (int j = i; j > 0; j--)//loop down from current number to find prime { if(i % j == 0) { matchCount++; } } if (matchCount == 2)//prime { primeCount++; result = i; if (primeCount == 10001) { break; } } } return result.ToString(); ; } } }

**My Solution after learning about primes and using Sieve of Eratosthenes:**

using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace Euler { class Problem7 : IProblemBase { //By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, //we can see that the 6^(th) prime is 13. //What is the 10001^(st) prime number? //The algorithm //1. Create a contiguous list of numbers from two to some highest number n. //2. Strike out from the list all multiples of two (4, 6, 8 etc.). //3. The list's next number that has not been struck out is a prime number. //4. Strike out from the list all multiples of the number you identified in the previous step. //5. Repeat steps 3 and 4 until you reach a number that is greater than the square root of n (the highest number in the list). //6. All the remaining numbers in the list are prime. public Problem7() { } private bool isPrime(int n) { if (n==1) { return false; } else if (n < 4) { return true; //2 and 3 are prime } else if (n % 2 == 0) { return false; } else if (n<9) { return true; //we have already excluded 4,6 and 8. } else if (n % 3 == 0) { return false; } else { int r= (int)(Math.Floor(Math.Sqrt((double)n))); // n rounded to the greatest integer r so that r*r<=n int f=5; while (f<=r) { if (n % f==0){return false;} //(and step out of the function) if (n %(f+2)==0){return false;} //(and step out of the function) f=f+6; } return true; //(in all other cases) } } public string GetAnswer() { int limit = 10001; int count=1; //we know that 2 is prime int candidate=1; do{ candidate=candidate+2; if (isPrime(candidate)) { count +=1; } } while(count<limit); return candidate.ToString(); } } }

Advertisements

## Leave a Reply