Grind Report 8

Problem 7

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?

*WARNING: This contains the solution!*

Coming up with a good way to do this required a little more thinking than previous problems. However, after some thought I came up with a fairly good approach.

First there are some helpful facts about prime numbers.

1. All prime number are odd except for 2.
   
2. For any number n that number can only have one prime factor greater than the squareroot of n. (This is n itself).

Knowing these two things we can significantly cut down on the amount of numbers to check.

In my solution I have a large array of ints containing all of the prime numbers found up to a certain point (foundCount). In this algorithm we consider every odd number greather than or equal to 3. Given this number, we check the previously found primes and see if it evenly divides the number. If so then the number is not a prime number. Because of fact #2 we know that if a prime number is greather than or equal to the squareroot of the number then the number is infact a prime number. So then we store the number into the prime array and continue along until the target prime number is found.

This is fairly basic and straight forward. Here is the code.

#include <iostream>
#include <math.h>
using namespace std;

const int TARGET = 10001;

int main()
{
 int primes[TARGET];
 primes[0] = 2;
 primes[TARGET - 1] = -1;
 int number = 3;
 int foundCount = 1;
 bool isPrime = false;
 while (primes[TARGET - 1] == -1)
 {
  double max = sqrt((float)number);
  //assume a number is prime until proven guilty
  isPrime = true;
  for (int i = 0; i < foundCount; ++i)
  {
   //break if the number is divisible by an already found prime number (guilty)
   if (number % primes[i] == 0)
   {
    isPrime = false;
    break;
   }
   //check to see if the square root of the number is less than or equal to the current prime number.
   //if so then break. This means the number is a prime.
   if (primes[i] >= max)
    break;
  }
  //add the prime number
  if (isPrime)
   primes[foundCount++] = number;
  //increment the number by 2 (to stay odd)
  number += 2;
 }
 int answer = primes[TARGET - 1];
 cout << "Answer: " << answer << endl;
}

*saved game*