Is it a prime number?

353 is a prime number. So is 7919 (in fact it is the 1000th prime). There are 25 primes between 1 and 100. From 1 to 1000 there are 168 of them.

It is difficult to check whether a number is prime or not. One simple method is to try and divide the number with smaller numbers. For example to find out whether 351 is a prime or not, you start checking by dividing the number by small numbers such as 2. Of course, it is an odd number so we immediately know that it is not divisible by 2. Next we try by 3 and it works! Indeed 117 times 3 is 351.

But suppose we working with 899. To check if it is a prime or not we start dividing it small numbers. 2 will not divide as the number is odd. But 3 will not divide either. If we keep on checking, we will see that up till 28 no number divides it (899 is $ 29 \times 31$).

How far should we check to be sure whether a number is prime or not? Suppose n is the number. Then we should try and divide 'n' with all prime numbers up till $( \sqrt n )$. Indeed if n is not a prime number then it must have a divisor smaller than or equal to $ ( \sqrt n )$ apart from 1. This fact has a simple proof.

Suppose n is not prime. Then it is composite (that is it has a divisor apart from 1 and it self).
Let p be a divisor of n. then $latex ( q =\frac{n}{p})$ is also a divisor of n.
That is n = pq
Now we claim that one of p or q is smaller than or equal to $( \sqrt n )$.
If our claim is false then both of them are greater than $( \sqrt n )$.
$ p > ( \sqrt n ) ; q > ( \sqrt n )$
This implies $ (p \times q > \sqrt n \times \sqrt n = n )$.
But p*q is not greater than n.
Hence our claim is correct.

Therefore when we have a number to check whether it is a prime or not, it is sufficient to try and divide it with all the prime numbers smaller than or equal to $ ( \sqrt n )$ (since if it is composite then it will have a divisor which smaller than or equal to $ ( \sqrt n )$ and this divisor is either itself prime or is divisible by a still smaller prime number).

Hence to check whether 641 is prime or not it is sufficient to check with all primes smaller than $( \sqrt {641} ) ~ 25$. That is we try to divide it with 2, 3, 5, 7, 11, 13, 17, 19, 23. None of them divides 641. Thus we conclude that it must be a prime.