6.21.2010

Problem 7 - Nth Prime [Project Euler Problems]

This problem requires you to give the 10001th prime number so I named it the Nth prime problem. It's pretty simple when you get to understand primes and appreciate them for their beauty. If you are a beginner in programming and haven't taken a course that covers runtimes, you may find this problem really annoying as you may spend much money on coffee while trying to stay awake watching and waiting for when the results will pop out on your screen. I finished this in less than 20 minutes (15 of those minutes were spent trying to figure out the truth behind these numbers).

The code I wrote is more interactive this time as it allows you specify the number of primes you want. Be careful; though this is relatively fast, if you input a really large number, you may have to leave your computer running for a couple hours.
The code is as below:
#include <iostream>
#include <list>
using namespace std;

int main (int argc, char * const argv[]) {
 
 // Number of primes the user will specify
 int numberOfPrimes;

 // STL container that dynamically stores all the prime numbers.
 list primes;

 // An iterator for loopint through this container.
 list::iterator primeIterator; 
 
 // This is the little trick. I know the first prime number is 2,
 // so that is injected into the list
 primes.push_back(2);
 
 // Request for the number of primes.
 cout << "Enter number of primes you want: ";
 cin >> numberOfPrimes;
 
 /* RUNTIME GUARD */
// if (numberOfPrimes > 999) {
//  cout << "Number is too large" << endl;
//  return 0;
// }
 
 /* Computation Loop 
  * This is where all compoputation is done.
  *
  * To do the wor are a couple new actors. 
  * Introducing the cast, we have: 
  *     i -> keeps count of the number of primes and makes
  * sure the user gets his required number.
  *     j -> presents numbers to be processed for 'prime'ness
  *     isPrime -> gets high when a 'j' is prime 
  * (This does not refer to hitting Js and getting high.
  * I meant it in the most programming terms possible).
  */
 for (int i = 0, j = 2; i < numberOfPrimes - 1; ++j) {
  bool isPrime = true;
  for (primeIterator = primes.begin();
    primeIterator != primes.end(); ++primeIterator) {
   if (j % (*primeIterator) == 0)
   isPrime = false;
  }
  if (isPrime) {
   // Add the number to the primes collection
   primes.push_back(j);
   ++i;
  }
 }
 
 // Print out the Nth prime number.
 primeIterator = primes.end();
 --primeIterator;
 cout << *primeIterator << endl;
 
 return 0;
}

The result is 104743.

No comments: