## 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. }