LOGIC TO FIND PRIME NUMBERS SIMPLEST WAY

INTRODUCTION

We all know that prime numbers play a great role in todays tech world from being used as “public key” for our credit/debit cards securing our purchases or any transactions we carry out online, to encrypting our important docs on our computer to keep it safe.

But as time passes the size of new prime numbers found out increases exponentially and the algorithms to find them are very limited as per my knowledge they are four in number,and all are pretty lengthy and time consuming in terms of machines which do all the finding work for us. As they carry out these algorithms through a number of basic steps,i.e., for machines this is a very hectic task.

Luckily for development of fast processing machines we can do that fast enough but wouldn't it be good if we could just reduce the steps to finding a number's primality???? So as I was looking through i found out a new way to do that and here I am with this algorithm to find a number is prime or not???

ALGORITHM

Take a number say 'X' to be checked for being prime or not.

Now check if the num is a perfect square ,i.e,whether square root of 'X' is an integer.

If 'X' is a perfect square the it is not a prime number.

Else divide the number 'X' by first four prime numbers,i.e,{2,3,5,7}.

if it is not divisible by any in list and is greater than 10 then divide it with all the other prime numbers >upto num/2 and if it is divisible by any of the prime numbers ,return false,i.e, it is not prime

If the number 'X' is NOT divisible by either of the four mentioned prime numbers then it is also a prime number,

Else the number 'X' is not a prime number.

Voila!!! as simple as that....

It reduces a series of looping,division and multipilcations needed to be performed in order to reach that conclusion of whether that number 'X' is prime or not.

Implemntation in code:

Here are few example of implementing above algorithm in some of well known and basic programming languages:

code for python:
import math
global n
def find_prime(num):
    prime=True
    sq=math.sqrt(num)
    if sq.is_integer():
        prime=False
    else:
        divisors=[2,3,5,7]
        if not num in divisors:
          for i in divisors:
            if num%i == 0:
              prime=False
              break
        if num>10 and prime:
             for i in range(2,(n/2+1)):
                 if n%i==0:
                        return False

   if prime:
        return True
   else:
        return False

n=input()
p=find_prime(n)
if p :
      print n,'is prime'
else:
      print n,'is not prime'

Explanation

First of all step1 mentioned in algorithm ,i.e.,taking in input,the number which is to be checked to be prime or not.

Then we check whether it is a perfect square or not because if it is a perfect square,i.e.,it's square root is an integer, then it has already got three divisors,i.e., 1,the number 'X' itself and its square root.

Hence no use of going any further as then the number 'X' will not be a prime number as it has got three divisors as mentioned above.

If the number 'X' is not a perfect square then we divide it with the first four prime numbers,i.e., 2,3,5 and 7, and if number 'X' is divisible by any one of the four numbers then it is not a prime number,elsewe check if num is greater than 10 if yes and is not divisibe by any of listed prime numbers then we check if it is divisible by any of prime numbers upto half of the num is is divisible then it is not a prime number,else it is .

How this happens is explained as follows:-

2 is the only even prime number to exist and as we know all other even numbers are divisible by 2.

So incuding 2 in the group of divisors excludes all the even numbers, which we know are not prime hence reducing the checking of all even numbers and saving us a lot of time.

After all even numbers being removed what is left are all odd numbers which all end with either 1,3,5,7 or 9.

Out of which all odds ending with 5 are divisible by 5.Hence removing them from list and reducing our time further as we know a prime number should only have two factors but ones ending with 5 have three already,i.e.,1,number itself and 5,hence they are not a prime number.

Left behind are the ones ending with 1,3,7,9. Of which most of numbers ending with 3,7 and 9 are divisible by 3 and the rest are either divisible by 7 or are prime numbers hence narrowing our search to a very limited group of numbers reducing our time by a handsome amount.

and the only numbers which are not prime and are not divisible by 2,3,5,7 are the product of next two prime numbers in series of prime numbers,only the product of alternate prime numbers!!! so we check in the last if number is divisible by any of prime numbers upto half of num or not.