A prime number is a positive natural number, whose value greater than 1 and has only two factors 1 and the number itself. In another word prime number only divided by itself and 1. Any positive natural number who is not a prime number is called composite number.

##### For example,

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

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

The primality is the method to determine whether the given number is prime or not. We can check the number is prime or not, to use a simple trial division method. If a number n is not divided by the number between the 2 and square root of n then this number is a prime number, this method is more than efficient compared to the trial division method.

#### Algorithm to check prime number using 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

#### Check Prime Number In C

There are many ways to check the number is the primer or not.Here, I am writing some program in c to find a prime number.

##### Example 1:

OutPut of the program:

##### Example 2:

It is almost same like example 1, here reduced the number of iteration to optimize the code.

OutPut of the program:

##### Example 3:

There is another efficient way to find the prime number.Instead of checking till n, we can check till the square root of n.

#### Find all the prime numbers less than or equal to a given integer n by Eratosthenes’ method:

1. First create a list of consecutive integers numbers from 2 to n: (2, 3, 4, …, n).
2. Initially, let q equal 2, the smallest prime number.
3. Find the all multiple of q by counting to n from 2q in increments of q, and mark them on the list. (these will be 2q, 3q, 4q, … ; the q itself should not be marked).
4. Find the first number greater than q in the list that is not marked. If there was no such number, stop. Otherwise, let q now equal this new number (which is the next prime), and repeat from step 3.

When the algorithm terminates, the numbers remaining not marked in the list are all the primes below n.

https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

#### Algorithms of Sieve of Eratosthenes

Input: an integer n > 1

Let A be an array of Boolean values, indexed by integers 2 to n,

initially all set to true.

Output: all i for which A[i] is true is the prime number.

##### Example:

To find all the prime numbers less than or equal to 15, proceed as follows.

• First, create an array of integers from 2 to 15 and initially mark all the element as a prime number.
2 3 4 5 6 7 8 9 10 11 12 13 14 15
• The first prime number in the list is 2, marked the every number in the list, which is multiple of 2.
2 3 4 5 6 7 8 9 10 11 12 13 14 15
• The next unmarked number in the list after 2 is 3, marked the every number in the list, which is multiple of 3.
2 3 4 5 6 7 8 9 10 11 12 13 14 15
• The next number not yet marked out in the list after 3 is 5, but 5*5 is greater than 15.So here we will stop the process because all member have been marked out at this point.

All unmarked number in the list are prime numbers.