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**