# How do you identify prime numbers?

Apr 9, 2016

#### Explanation:

I understand we are trying to identify larger primes, say at least more than $20$. Further, let us try to divide the number only with prime numbers, as in case they are divisible by a composite number, they will be divisible by its prime factors too.

One of simplest thing that comes to one, who is trying to identify prime numbers, is that a prime number does not have in unit's digit $\left\{0 , 2 , 4 , 5 , 6 , 8\right\}$, as the number will then will be divisible by $2$ and $5$. Also sum of all the digits should not be divisible by $3$. These too themselves will remove a large number of composites.

Another important thing is that one need not try all the primes (other than $\left\{2 , 3 , 5\right\}$, which we have already eliminated).

If the number is $n$ and the prime number just below its square root is $m$, then we should try only till $m$. The reason is that if a prime number up to less than $m$ does not divide $n$, then no other than prime will divide it.

As if $n$ has a factor greater than $m$, say it is $x$ and other factor is $y$ i.e. $x \cdot y = n$, then $y = \frac{n}{x} < m$.

Even for trying to divide by a somewhat large number, one could check using a calculator and if quotient is in decimal fraction, move to next prime number.