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:
Get script arguement (N = max prospect)
Record start time
Write arguement N to log file
Write 2 & 3 as first two primes to CSV result file
ARRAY A(1, 2) = (2, 3)
Set found counter, CNT = 2
FOR M = 4 to N
FOR EACH ARRAY A (P)
If P > SQRT(M), then prime, save to ARRAY A(MAX+1).
If M modulus P = zero, then non prime, exit for
Otherwise, save prime number to ARRAY A (MAX+1)
Write ARRAY A(MAX) to CSV result file as next prime number
Increment found counter, CNT++
Write number of primes found, CNT, to log file
Record end time
Calculate & write time elapsed to Log file
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.