Sunday, May 22, 2016

Find prime numbers by script

It's been more than one year since I posted last time. Actually, I was busy with my job. 
I'm not a programmer, but I often write a script to extract specific data from numerical simulation results and to make some input sequence files for simulation. When it comes to this type of work, Perl seems to be better than others according to web evaluation. 
One day, I heard news that the longest prime number was found by the computer, and I became wondering how long does it take to find prime numbers by a Perl script. 

 Here is a script to find numerical numbers up to N.

# script to find prime numbers to N
$N=100000;
# 2 is an exceptional number to this script
print "2\n";
$numP=1;
# start to find prime numbers from 3
for($k=3;$k<=$N;$k+=2){
        $m=2;
        until($k%$m==0){
        $m++;
        }
        if($k==$m){
        print "$k\n";
        $numP++;
        }
}
print "\n";
print "the number of prime number to $N is $numP\n";

In this script, I take the number 2 as an exceptional one, and try to find prime numbers from 3 in for-loop. For each $k over 3, modulo is performed from 2 to $k until 0 is found. if $k is dividable by itself, then it is a prime number. To save time, even numbers are skipped.

I compared the process time of three computers by using build-in function "time" in Linux.
time perl scriptname.pl
As is set above script, I run the script to find numbers up to 100,000. Here are comparison results.
 8 minutes -- Raspberry Pi 2 model B 
36 seconds -- Mac book pro 2012
17 seconds -- Company Linux machine
This makes sense to me in terms of computer spec. Company machine is as powerful as being able to run the advanced spice simulator easily and memory is also over 100G.

When $N increases, then the process time also increases exponentially. Try it.

I'm now thinking to write a script to calculate pi next.

No comments:

Post a Comment