Before we check whether a number is prime or not, we should know the answer for the question "What is a prime number ?"

Definition : A number which is only divisible by 1 and itself is a prime number. For example, numbers such as 1, 2, 3, 5, 7, 11 etc. are not divisible by any numbers other than 1 and themselves. So, they are all prime numbers. But, the numbers such as 4, 6, 8, 16 etc., are divisible by 2 and hence they are non-prime numbers. The number 9 is divisible by 3 and hence it is also no-prime number. Now, let us see " How to check whether a given number is prime or not?"

Procedure : Consider the number 16. It is not divisible by 9, 10, 11, 12, 13, 14 and 15 which are all greater than 16/2. So, the first point to remember is:

- A number m cannot be divisible by a number which is greater than m / 2.

In our case m is 16. It is divisible by the numbers 2, 4 and 8 which are less than or equal to 16/2.

The second point to remember is:

- A number m may be only divisible by either 2 or 3 or 4 or 5 ..... or m/2.

So, to check whether m is prime or not, it is sufficient to divide m by the numbers 2, 3, 4....m/2 one after the other. During this process, if the remainder is zero, the number m is non-prime.

But, even after dividing m by all the numbers from 2 to m/2, if the remainder is still not zero, the number m is prime.

**The partial code is as follows**

for (i=2; i<=m/2; i++)

{

if(m%i == 0)

{

printf("The number is non-prime");

exit(0);

}

}

printf("The number is prime\n");

The algorithm and the equivalent flowchart are shown below:

**Algorithm : PRIME**

[This algorithm checks whether the given number is prime or not.]

**Step 1**: [Enter the number]

Read: n

**Step 2**: [Check for prime number]

for i=2 to n/2 in step 1

if(n%i == 0)

Write : 'Number is non-prime'

Exit.

[End of if]

[End of for]

**Step 3**: [Output prime]

Write: 'number is prime'

**Step 4**: [finished]

Exit.

The complete program to check whether the given number is prime or not is shown below:

Example : Program to check whether a number is prime or not.

**Program**

#include<stdio.h>

#include<stdlib.h>

main( )

{

int n, i;

printf("Enter a number:\n");

scanf("%d",&n);

for(i=2; i<=n/2; i++)

{

if(n%i == 0)

{

printf("%d is non-prime",n);

exit(0);

}

}

printf("%d is prime",n);

}

**TRACE 1**

**Input**

Enter a number

13

**Computations**

i=2 3 4 5 6

13/2 13/3 13/4 13/5 13/6

2,3,4,5,6 can't divide 13

**Output**

13 is prime

**TRACE 2**

**Input**

Enter a number:

9

Computations

i=2 3 4

9/2 9/3

**Output**

9 is non-prime

## 0 comments:

## Post a Comment