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 in which the number is only divisable by one and itself.
The Algorithm that I am going to introduce is a brute force method for calculating prime numbers. It is great for comparing the computing power of two machines by looking at overall execution times.
This routine consists in dividing n by each integer m 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, it is a prime.
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:
Calculating Primes Algorithm:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
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 NEXT P 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++ NEXT M 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 87 seconds on a Dell i5 Laptop running Windows 7 – 32 bit operating system and found 183,072 prime numbers.
| prg-calc-primes-v1.pl | Calculate Primes Program |
| primes.cmd | Primes Batch File |
| primes.log | Primes Log File |
| primes.csv | Primes Result File |
| image | DOS Output Screen |
