Tuesday, November 29, 2011

Find nth Prime Number in C++

c++ program to find prime numbers:


The problem of finding prime number can be solved by checking all numbers, testing them for prime and then moving ahead. If you want to calculate nth prime. Then this can be done in a brutal way by checking the number one by one. This may sound odd, by there is no easy way then this  for prime numbers (Well Actually there are like Pollard's Rho Algorithm, Number Sieves or Shor's Quantum Algorithm, but we are talking about the one that most people may understand easily). There may be way to pre-calculate the prime numbers but that again is not sufficient. So how can we use c++ to create a program to find prime numbers.

Method:
The method is pretty similar to what i have discussed in my other post.
http://programs-in-c-plus-plus.blogspot.com/2011/09/program-to-find-nth-prime-number-in-c.html
To convert it into a c++ program , we will just encapsulate the main functions into one single class. That class will serve us for calculations. The class has a member variable "n" , which can be used to calculate "nth" prime. There will be 2 methods to set this "n" variable. One is an overloaded constructor, other is a member function. Choice is yours.

Code:

#include <iostream>
using namespace std;


class prime
{
    int n;// this will be used to find the nth prime
    public:
    prime()
    {
        n=1;//default value 1
    }
    prime(int t)
    {
        n=t;//set n by using constructor
    }
    void setGoal(int k)
    {
        n=k;//set n by function
    }
    void find()// find the prime
    {
        int count=0;
        long a = 2;
            
        while(count<n)
        {
            
            long b = 2;
            int prime = 1;
            while(b * b <= a)
            {
                if(a % b == 0)
                {
                    prime = 0;
                    break;
                }
                b++;
            }
            if(prime)
            {
                count++;
            }
            a++;
        }
        cout<<"\n The "<<n<<" th prime="<<--a;
    }
};
int main()
{
    prime p;
    p.setGoal(10);
    p.find();

}