Calculating Primes – Part 2

Today I am going to talk about calculating primes.

Not the Transformer movie in which Optimus Prime has to help the humans save the world.

I am talking about prime numbers, a postive integer that is only divisable by one and itself.
All other integers, greater than 1 are non-prime, composite numbers.

We are going to refine the algorithm for calculating prime numbers by using the the fundamental theorem of arithmetic. Any positive integer can be divided in primes in essentially only one way. The phrase ‘essentially one way’ means that we do not consider the order of the factors important.

This routine consists in dividing N by each prime number P which is greater than 1 and less than or equal to the square root of N. If the result of any of these divisions is an integer, then N is not a prime; otherwise, N is a prime. I will be using a PERL array to store and retrieve the list of primer numbers.

Most of the PERL coding used standard, built-in functions.

One exception was the date calculation package (Date::Calc) that I down loaded from CPAN to calculate the total elapsed time of the program. There is a bug in the perl package installer from Active State. Afer commenting out the offending line in web.pm, I used the command line ‘ppm install Date::Calc’ to add the package.

I always like to create a high level program algorithm before starting any coding. I usually write it in psuedo code so that is program like in nature.

Calculating Primes Algorithm:

The table below has the PERL script used in the solution and various supporting / output files. I ran the program to calculate all the prime numbers less than or equal to 2.5 Million. The program executed in 25 seconds on a Dell i5 Laptop running Windows 7 – 32 bit operating system and found 183,072 prime numbers.

prg-calc-primes-v2.pl Calculate Primes Program
primes.cmd Primes Batch File
primes.log Primes Log File
primes.csv Primes Result File
image DOS Output Screen

 

 

 

 

In summary, this new algorithm is 3.48 times faster than the original one. Therefore, taking time to understanding the business problem and applying a better solution will increase overall performance. This is critically important if the maximum prime number was 100 Million and the script ran every day.

Related posts

Leave a Comment