C Program to find Prime Number

A prime number is a positive natural number, whose value greater than 1 and it has only two factors 1 and the number itself. Either you can say that prime numbers only divided by itself and 1. Any positive natural number who is not a prime number is called a composite number.

For example,

2,3,5,7,11..
In the above example, 2 is the (smallest) prime number because it has only two factors 1 and 2.

Note: 1 is not a prime or composite number and 2 is the only even prime number.

Using the trial division we can check the prime number in C but it is a slow method to check the prime number. In which we need to check whether given number n is a multiple of any integer between 2 and the square root of n.

We can also use faster algorithms include the Miller–Rabin primality test, which is fast but has a small chance of error, and the AKS primality test, which always produces the correct answer in polynomial time but is too slow to be practical.

Algorithm to check prime number using trial division method

START

Step 1 → Take the number n

Step 2 → Divide the number n with (2, n-1) or (2, n/2) or (2, sqrt(n)).

Step 3 → if the number n is divisible by any number between (2, n-1) or (2, n/2) or (2, sqrt(n)) then it is not prime

Step 4 → If it is not divisible by any number between (2, n-1) or (2, n/2) or (2, sqrt(n)) then it is a prime number

STOP