Posted in C++

Prime numbers

Prime numbers (Definition) :-

A prime number (or a prime) is a natural number greater than 1 that has no positive divisors other than 1 and itself.

Now the numbers which are prime follow the above condition. If we ask to write a program which identifies a prime number, the first approach would be by brute force, i.e to check for every number between 2 and the number itself and then use a flag to indicate whether a our program found a divisor or not. Then on the basis of the value of the flag we can say if it is a prime number or not.

This approach is very first thought but if we ask the computer to search for prime numbers in the range of around 1000000. Now checking every number would surely be lot more time taking.

I want to optimize my code for such cases. Now I would apply mathematics,

Let us see if the given number is even (divisible by 2) then we can surely say it is not prime(with an exception of 2). With this I deduce that it is irrelevant to check for divisibility with any even number.

Now we cut our search to only those cases where divisor is odd.

I use another fact that an odd number‘s divisor has to be less than half of it. So I will check it’s divisibility by odd numbers only till half of it and arrive at my conclusion. So I have optimized my code by at least 3 times.

I can still optimize it further following the same logic (like checking divisibility by 3 and shortlist my search till 1/3 rd  of N and so on) but I leave it as an exercise (it is possible  !!!).

Glimpse of my fully optimized code (uses recursion) :

Prime Number
Fully optimized program for prime numbers
Prime Number
Fully optimized program for prime numbers

Partly optimized code  (one given here) :

Prime Number
Fully optimized programe for prime numbers
Prime Number
Fully optimized programe for prime numbers

Final code (not fully optimized one).

Post Script : Real Difference comes in checking prime numbers not the composite ones. You can note above that on my machine partly optimized code will take less time for composite number’s but it takes a lot more time to compute prime numbers.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s