Post date: Jun 29, 2013 12:22:48 AM
Problem
Write a function to calculate the nth prime number:
N = 0; Prime#: 2
N=1; Prim#: 3
What is the complexity of this algorithm
Solution
/*
============================================================================
Author : James Chen
Email : a.james.chen@gmail.com
Description : Calculate the nth prime number
Created Date : 29-Jun-2013
Last Modified :
============================================================================
*/
#include <iostream>
#include <iomanip>
#include <vector>
using namespace std;
int FindNextPrime(vector<int>& primes)
{
int candidate = primes[primes.size() - 1] + 2;
while(true){
int i = 0;
while(i < primes.size()){
if(candidate % primes[i] == 0) break;
if(candidate < primes[i] * primes[i]) return candidate;
i++;
}
if(i == primes.size()) break;
candidate += 2;
}
return candidate;
}
int CalclulateNthPrime(int n)
{
vector<int> primes;
primes.push_back(2);
primes.push_back(3);
primes.push_back(5);
primes.push_back(7);
if(n < 4) return primes[n];
while(primes.size() < n + 1){
int candidate = FindNextPrime(primes);
primes.push_back(candidate);
}
return primes[n];
}
int main(int argc, char* argv[])
{
for(int i = 0; i < 30; ++i){
cout << "The " << setw(2) << i << "th prime is ";
cout << CalclulateNthPrime(i) << endl;
}
return 0;
}
Output
The 0th prime is 2
The 1th prime is 3
The 2th prime is 5
The 3th prime is 7
The 4th prime is 11
The 5th prime is 13
The 6th prime is 17
The 7th prime is 19
The 8th prime is 23
The 9th prime is 29
The 10th prime is 31
The 11th prime is 37
The 12th prime is 41
The 13th prime is 43
The 14th prime is 47
The 15th prime is 53
The 16th prime is 59
The 17th prime is 61
The 18th prime is 67
The 19th prime is 71
The 20th prime is 73
The 21th prime is 79
The 22th prime is 83
The 23th prime is 89
The 24th prime is 97
The 25th prime is 101
The 26th prime is 103
The 27th prime is 107
The 28th prime is 109
The 29th prime is 113
Press any key to continue . . .