{"id":2346,"date":"2012-07-11T17:07:42","date_gmt":"2012-07-11T17:07:42","guid":{"rendered":"http:\/\/craftydba.com\/?p=2346"},"modified":"2024-02-17T14:28:36","modified_gmt":"2024-02-17T14:28:36","slug":"calculating-primes-part-2","status":"publish","type":"post","link":"https:\/\/craftydba.com\/?p=2346","title":{"rendered":"Calculating Primes – Part 2"},"content":{"rendered":"

Today I am going to talk about calculating primes.<\/p>\n

Not the Transformer movie<\/a> in which Optimus Prime has to help the humans save the world.<\/p>\n

I am talking about prime numbers<\/a>, a postive integer that is only divisable by one and itself.
\nAll other integers, greater than 1 are non-prime, composite numbers.<\/p>\n

We are going to refine the algorithm for calculating prime numbers by using the the fundamental theorem of arithmetic<\/a>. 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. <\/p>\n

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<\/a> to store and retrieve the list of primer numbers. <\/p>\n

Most of the PERL coding used standard, built-in functions. <\/p>\n

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

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.<\/p>\n

Calculating Primes Algorithm:<\/span><\/p>\n

\r\nGet script arguement (N = max prospect)\r\nRecord start time\r\nWrite arguement N to log file\r\nWrite 2 & 3 as first two primes to CSV result file\r\nARRAY A(1, 2) = (2, 3)\r\nSet found counter, CNT = 2\r\nFOR M = 4 to N\r\n  FOR EACH ARRAY A (P)\r\n      If P > SQRT(M), then prime, save to ARRAY A(MAX+1).\r\n      If M modulus P = zero, then non prime, exit for\r\n  NEXT P\r\n  Otherwise, save prime number to ARRAY A (MAX+1)\r\n  Write ARRAY A(MAX) to CSV result file as next prime number\r\n  Increment found counter, CNT++\r\nNEXT M\r\nWrite number of primes found, CNT, to log file\r\nRecord end time\r\nCalculate & write time elapsed to Log file<\/pre>\n
<\/P><\/p>\n
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.<\/p>\n\n\n\n\n\n\n\n
prg-calc-primes-v2.pl<\/a>\n<\/td>\nCalculate Primes Program<\/td>\n<\/tr>\n
primes.cmd<\/a>\n<\/td>\nPrimes Batch File<\/td>\n<\/tr>\n
primes.log<\/a>\n<\/td>\nPrimes Log File<\/td>\n<\/tr>\n
primes.csv<\/a>\n<\/td>\nPrimes Result File<\/td>\n<\/tr>\n
image<\/a>\n<\/td>\nDOS Output Screen<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n
 <\/p>\n
 <\/p>\n
 <\/p>\n
 <\/p>\n
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.<\/p>\n","protected":false},"excerpt":{"rendered":"
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…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[7],"tags":[489,488,486,487],"class_list":["post-2346","post","type-post","status-publish","format-standard","hentry","category-other","tag-argv","tag-arrays","tag-cpan-perl-modules--datecalc--free-code--john-f-miner-iii--perl-script--prime-numbers","tag-fundamental-theorem-of-arithmetic"],"_links":{"self":[{"href":"https:\/\/craftydba.com\/index.php?rest_route=\/wp\/v2\/posts\/2346","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/craftydba.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/craftydba.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/craftydba.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/craftydba.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=2346"}],"version-history":[{"count":0,"href":"https:\/\/craftydba.com\/index.php?rest_route=\/wp\/v2\/posts\/2346\/revisions"}],"wp:attachment":[{"href":"https:\/\/craftydba.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=2346"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/craftydba.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=2346"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/craftydba.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=2346"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}