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
3. def isPrime_basic(n):
4.     for i in range(2,n):
5.         if n%i==0:
6.             return False
7.     return True
9. if __name__=='__main__':
10.     n=raw_input('Enter No to test isPrime :- ')
11.     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;
6. #include<stdio.h>
7. #include<math.h>
8. int isPrime(int n){
9.         int i,sqrt_n,flag=1;
10.        
11.        
12.                 sqrt_n=(int)sqrt(n); //squire root of n
13.                 sqrt_n++; //approximating
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. }
33. main(){
34.         int arr[300];
35.         int i,j;
36.         for(i=1;i<300;i++){
37.                 arr[i]=i+1;
38.         }
39.         arr[0]=-1; //special case for 1
40.         for(i=0;i<300;i++){
41.                 if(arr[i]!= -1){
42.                         if(isPrime(arr[i])==0){
43.                         arr[i]==-1;
44.                    }
45.                    else{
46.                         for(j=i+arr[i];j<300;j=j+arr[i]){
47.                                 arr[j]=-1;
48.                            }
49.                    }
50.            }
51.         }
52. //print prime no
53. cout<<"prime no are :-"<<endl;
54. for(i=0;i<300;i++){
55.         if(arr[i]!= -1){
56.                 cout<<" "<<arr[i];
57.         }
59. }      
60. }