Prime number is one of most frequent thing we face in programming Problems . But you know most time we use algorithm to test number is prime or not is is very slow if number is too big . In other word our algorithm is not efficient .

But little bit change to that algorithm make it more efficient .

Now lets Modify above Program to increase its speed . i.e. number of steps .

Let number Be N

and let say it is Not prime number than

i.e.

Now you can modify above code i.e check its divisibility in range 2 to sqrt(N).

But little bit change to that algorithm make it more efficient .

#### Prime number :

A integer that has no integral factor except 1 and itself . ( 1 is not treated as prime number )

Now normal Way to solve this is make a for loop from 2 to N/2 & check divisibility for each integer .

`// check given no is`** prime or NO**t
#include<stdio.h>
void check_prime(int N)
{
int i,flag=0;
for(i=2;i<**=***N/2*;i++) //check for each num between 2 & n/2
{
**if(N%i ****=****= 0)**
{
flag=1;
break;
}
}
if(flag==0)
printf("\nPrime");
else
printf("\n NOt Prime");
}
void main()
{
int N;
printf("Enter No to Check : ");
scanf("%d",&N);
**check_prime(N);** //call function to check
}

#### OutPut :

Let number Be N

and let say it is Not prime number than

**N = a*b**where a and b less than or equal to squre root of N

i.e.

*a,b <= sqrt(N) (*Why ...???) this is basic mathematics .. So you have to interpret it by yourself .if you find out comment here with your reason .

Now you can modify above code i.e check its divisibility in range 2 to sqrt(N).

#### C code :

`// check given no is `**prime or NOt**
#include<stdio.h>
#include<math.h>
void ch_prime(int N)
{
int i,sq,flag=0;
sq=sqrt(N); //finding squire root
for**(i****=2;i****<=sq;i++)**
{
if(N%i == 0)
{
flag=1;
break;
}
}
if(flag==0)
printf("\nPrime");
else
printf("\n NOt Prime");
}
void main()
{
int N;
printf("Enter No to Check : ");
scanf("%d",&N);
ch_prime(N);
}

Now lets further optimize it .

Now think if a number can't divide by 2 then it must not be divided by any even number .

so you don't have to check at even number . it reduce your number of steps by half .

this is really great achievement .

Now its time to implement it .

####
**C Code :**

- // check given no is prime or NOt
**/*****main concept :****we have to check its divisibility from 2 to sqrt(N)****&&****if a number is not divisible by 2 than it is also not divisible by even numbers*****/**- #include<stdio.h>
- #include<math.h>
- void check_prime(int N)
- {
- int i,sq,flag=0;
- sq=sqrt(N);
- if(N%2 != 0)
**//if number is not divisible by 2** - {
- for(i=3;i<=sq;i=i+2) //then start from three & increment by 2 till sqrt(N)
- { // divide by above term to check it is prime
- if(N%i == 0)
- {
- flag=1; //flag counter =1 conform it is not prime
- break;
- }
- }
- }
- else
- flag=1;
- if(flag==0)
- printf("\nPrime");
- else
- printf("\n NOt Prime");
- }
- void main()
- {
- int N;
- printf("Enter No to Check : ");
- scanf("%d",&N);
- if(N==2)
**// 1 & 2 is treated as special case** - printf("\nPrime Number");
- else if(N==1)
- printf("\nNot a Prime Number");
- else
- check_prime(N);
- }

Can we further optimise it . yes we can .

similar to concept of even number now think if number is not divisible by 3 then also not divisible by multiple of three . similar concept is applicable for 5,7 and so on ..

but till Now I can't find efficient way to implement this

If you found please share with us .

thanks Have a Nice day !!!

What's up to all, for the reason that I am actually eager of

ReplyDeletereading this webpage's post to be updated regularly. It carries nice information.

Feel free to surf to my homepage: Cheap Dr Dre Beats

Hello friends, how is all, and what you wish for

ReplyDeleteto say on the topic of this paragraph, in my view

its actually amazing for me.

My site - Beats By Dr Dre