Monday, 30 March 2015

n'th Prime Number

The first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 5th prime is 11. 
What is the 10001st prime number???

This Question is quit direct but we try to solve it in very effective way.
i.e with less complexity .


First Of all we need to know best way to check a number is prime or not. Read this Play With Prime .


Now We gonna use similar approach as we use to check isPrime or not.
i.e at least we can escape all even number before checking.

Algorithm:
  1. initially initially count=1 (we count=1 as 2 is prime but we r not gonna calculate it in our program) 
  2. initialize i=3 (start checking prime from 3)
  3. while( i < n){ if i is prime increment count by 1 , increment i by 2 after each loop}
  4. i-2 is our required prime number
Here we eliminate almost half of number before checking it is prime or not.

C-Program To find n'th Prime Number:


  1. //C-Program to find n'th prime number
  2. //www.codecops.in
  3. #include<stdio.h>
  4. #include<math.h>
  5. int isPrime(int n){
  6.         /*
  7.          *****<math.h>
  8.          this Function take n is input
  9.          & return 1 if n is prime else return 0
  10.         */
  11.         int i,sqrt_n,flag=1;
  12.                 sqrt_n=(int)sqrt(n); //squire root of n
  13.                 sqrt_n++;
  14.         if(n<2){
  15.                 return 0; //return False
  16.         }
  17.         else{
  18.                 if(n==2){
  19.                         return 1; //return True
  20.                 }
  21.                 else if(n%2==0)
  22.                         return 0;
  23.         }
  24.         for(i=3;i<sqrt_n;i=i+2){
  25.                 if(n%i==0){
  26.                         flag=0;
  27.                         break;
  28.                 }
  29.         }
  30.         return flag; //return value of flag 0(false) or 1(true)
  31. }
  32. int main(){
  33.         int count=1; //we include 2 as first prime number
  34.         int i,n;
  35.         printf("\nEnter Value of n :");
  36.         scanf("%d",&n);
  37.         i=3;//avoid checking even numbers by incrementing index by 2
  38.             //after each itteration
  39.         while(count<n)
  40.         {
  41.                  if(isPrime(i)){
  42.                         count++;
  43.                  }
  44.                  i=i+2;
  45.         }
  46.     printf("\nnth prime number is %d",i-2);
  47. }

Please Suggest ,

Thank U

No comments:

Post a comment

THANKS FOR UR GREAT COMMENT

Blogger Widgets