Problem 7: Nth prime

Q. What is the 10001st prime number?
Sol:
I got the idea to solve this problem from the algorithm "Sieve of Eratosthenes"  which finds the prime numbers upto a number. It just stores the number in an array selects one element of the array at a time in ascending order and eliminates the numbers in the array which come out to be multiple of the selected.
If we start constructing an array starting with array values 2 and 3(the first two prime numbers) and then continue to incorporate the numbers in the array which are not multiple of previous values in array, we will always get a prime number in the array. Moreover it can be observed that any prime number can be expressed as (6x+1) or (6x-1). So, there is no need to check other numbers for divisiblity by numbers in array.


Then, the algorithm is that we start from 2 and 3 as initial values in array, increment a variable so that it has always the value of the form 6x+1 or 6x-1 and check if not divisible by elements already present in the array. If not divisible by any one of them, the number is entered into the array.


Now, comes the fun part........ coding


#include< cstdio>
using namespace std;

int main()
{
    int n;
    scanf("%d",&n);
    int arr[100000];
    int i=2;
    arr[0]=2;
    arr[1]=3;
    int k=1,j;
    int nextprime,flag=0,c=1;
    nextprime=5;
    while(i < n)
    {
               flag=0;
               for(j=0;((j < i)&&(arr[j]<=sqrt((double)nextprime)));j++)
               {
                               if(nextprime%arr[j] == 0)
                               {
                                              flag=1;
                                              break;
                               }
               }
               if(flag==0)
               {
                          arr[i]=nextprime;
                          i++;
               }
               if(c==-1)
                        k++;
               nextprime=6*k +c;
               c=-c;
    }
    printf("%d\n",arr[n-1]);
}


In the program, a variable k is is used to find the next element (which is 6k+1 or 6k-1) to be considered for position in the array.The element is checked for divisiblity and entered into array if not divisible by any of the numbers in the array....




Please post your comments and doubts...
Suggestion for better algorithms are always welcome.....