Thursday 8 January 2015

Play With Prime

Prime numbers :- Numbers that are only divisible by 1 and by itself .

Now think how to check number is prime or not

Basic Approach

 Check Divisibility of number form 2 to n-1 is it is not divisible then prime .




  1. #Just check for divisibility by all No except 1 & n
  2. def isPrime_basic(n):
  3.     for i in range(2,n):
  4.         if n%i==0:
  5.             return False
  6.     return True
  7. if __name__=='__main__':
  8.     n=raw_input('Enter No to test isPrime :- ')
  9.     print isPrime_basic(int(n))

but you can imagine complexity increase with value of n .So we need to find some better Approach

Better Approach

We can make above code run faster by noticing that we only need to check divisibility for values of i that are less or equal to the square root of n.      { Think Why ?? }

And

As we know 2 is only even prime Number . so remove all multiple of 2 because they are not  prime and if a number is not divisible by 2 then it will also not divisible  by any other even Number.

  1. def isPrime(n):
  2.     if n<=1:
  3.         return False
  4.     elif n==2:
  5.         return True
  6.     elif n%2==0:
  7.         return False
  8.     elif n>2:
  9.         for i in range(3,n,2):
  10.             if n%i==0:
  11.                 return False
  12.         return True
  13. if __name__=='__main__':
  14.     n=int(raw_input('Enter number to check isPrime :- '))
  15.     print isPrime(n)

Fastest Technique to find all prime no below given Number : 

This technique is known as sieve of eratosthenes . In this Technique 
  • Create  list of number from to to n.
  • find first prime then remove all its multiple from the list Ex: 2 is first prime number then remove 4,6,8,10 ... from the list. similarly remove multiple of next prime numbers like next prime number is 3 . Now  remove its multiple i.e. 6,9,12,15 ...
  • Repeat process until reach to the end of list
  • Remaining element in list is prime numbers
There are many way to implement this . you can find many solution for this ,But try once before search it on google

A sample Program  in C++ for this . This is cheapest implementation this algorithm but You can use this program to understand this algorithm.

  1. //C++ Program to calculate prime number between between 1 to 300
  2. #include<iostream>
  3. #include<math.h>
  4. using namespace std;
  5. #include<stdio.h>
  6. #include<math.h>
  7. int isPrime(int n){
  8.         int i,sqrt_n,flag=1;
  9.        
  10.        
  11.                 sqrt_n=(int)sqrt(n); //squire root of n
  12.                 sqrt_n++; //approximating
  13.         if(n<2){
  14.                 return 0; //return False
  15.         }
  16.         else{
  17.                 if(n==2){
  18.                         return 1; //return True
  19.                 }
  20.                 else if(n%2==0)
  21.                         return 0;
  22.         }
  23.         for(i=3;i<sqrt_n;i=i+2){
  24.                 if(n%i==0){
  25.                         flag=0;
  26.                         break;
  27.                 }
  28.         }
  29.         return flag; //return value of flag 0(false) or 1(true)
  30. }
  31. main(){
  32.         int arr[300];
  33.         int i,j;
  34.         for(i=1;i<300;i++){
  35.                 arr[i]=i+1;
  36.         }
  37.         arr[0]=-1; //special case for 1
  38.         for(i=0;i<300;i++){
  39.                 if(arr[i]!= -1){
  40.                         if(isPrime(arr[i])==0){
  41.                         arr[i]==-1;
  42.                    }
  43.                    else{
  44.                         for(j=i+arr[i];j<300;j=j+arr[i]){
  45.                                 arr[j]=-1;
  46.                            }
  47.                    }
  48.            }
  49.         }
  50. //print prime no
  51. cout<<"prime no are :-"<<endl;
  52. for(i=0;i<300;i++){
  53.         if(arr[i]!= -1){
  54.                 cout<<" "<<arr[i];
  55.         }
  56. }      
  57. }

No comments:

Post a Comment

THANKS FOR UR GREAT COMMENT

Blogger Widgets