How do you identify prime numbers?

1 Answer
Apr 9, 2016

Please see below.

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 #{0,2,4,5,6,8}#, 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 #{2,3,5}#, 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*y=n#, then #y=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.