# 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