Test whether a number is prime

Problem Definition: To verify whether an integer is prime or not.

Problem Analysis: Prime number is an integer which is exactly divisible by 1 and itself.

For example, 17 is a prime number because 1 and 17 are the only two factors of 17.

Generalizing this, a positive integer with just two factors is a prime number.

Examples of prime numbers are 2, 3, 5, 7, 11, 13, ......

To verify whether a number (say) is prime or not, divide the number by 2 to n 1.

If the remainder is zero in any of the cases, then the number is not prime (such numbers are called composite).

Mathematically, it is also enough to divide the number from 2 to √n

Solving by Example: Let us take two numbers 37 and 49.

Consider 37 first. The square root of 37 is 6 (approximately).

Now, divide 37 by 2, 3, 4, 5 and 6.

None of the division operation gives a remainder of zero.

Hence, 37 is a prime number. Now, let us consider 49.

The square root of 49 is 7.So let us divide 49 by 2, 3, 4, 5, 6 and 7.

As 49 is divisible by 7, it is not a prime numbers.

Algorithm Definition

Step 1: Start

Step 2: Read the number n which we want to verify whether prime or not.

Step 3: Initialize the value of the divisor i as.

Step 4: Repeat the following steps till i less than or equal to square root of n. or the remainder of the division operation is zero.

(i) Divide n by i

(ii) if remainders is zero, then prints the number is not prime and exit the process.

Step 5: If none of the remainders are zero, print n is a prime number.

Step 6: Stop