Prime Number Program with detail explanation step by step - UCS - Unleash-Coding-Skills

Wednesday, 21 March 2018

Prime Number Program with detail explanation step by step - UCS


What is a prime number??


A number is said to be a prime number if it is only divisible by 1 and only itself.

Yes, you are on the correct path.

Simple apply this statement to know wheather a number is prime or not.

Let us consider a loop for this number.Let the number be 'n'.The loop must run from 1 to (n/2) since after (n/2) no number will be factor of the n except the number itself.
For example 6 the factor of 6 are 1 3 6
(n/2) => 6/2=3

So we have 1 and 3 as factors in that range.

Similarly consider 10: the factors are 1, 2,5,10.
(n/2) => (10/2) => 5 it is enough to check up tp 5.

if no number in the range up to 5 is not factor of the n other than 1 then it is prime number.

Let us run a loop  for above assumptions.

for( int i= 1;i<=(n/2);i++)
{
//This loop will run as per our rules up to n/2
}
Now you are in the right way.So whats the logic we must check wheather a number is divisble or factor of another number.

Suppose 6 is divisible by 1 ,2,3.
Perform modulo operation 6%1=0, 6%2=0, 6%3=0.

So we are half way done.A number is a factor to another number if it (number(n) % (our number in loop) =0)
So we need to take count how many numbers in that loop are factor of that number.so initialize count with '0' then start applying logic.

n=take input
count=0;
for(int i=1;i<=n/2;i++)
{
if(n%i==0)
count=count+1;
}
So now you have a count of number of factor for that number less than or equal to (n/2).if the count equals to 1 then the number is "prime" other wise it is not prime.The complete program is C language below.

#include <stdio.h>
int main()
{
int i,count=0,n;
scanf("%d",&n);
for(i=1;i<=n/2;i++)
{
if(n%i==0)
count=count+1;
}
if(count==1)
printf("%d is a prime number",n);
else
printf("%d is not a prime number",n);
}

Cool , you have done learning  prime number ,keep going.
Note: It is just for beginners to programming lots of optimizations can be done in that for better understanding I made it simple.
Happy Coding.

No comments:

Post a comment