Calculate Prime Numbers with Perl

There are several ways to calculate primes. Probably, the most efficient one is recursively dividing a number with all primes lower than the number itself. Since no primes are divisible by numbers other than themselves and 1, it would be possible to divide a number with all numbers below it. All numbers are essentially built up of primes, and therefore we can safely skip dividing by numbers which are not primes themselves, speeding up the process significantly.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

# The array where the primes will be stored
my @primes = (2);
# The maximum number of iterations
my $max = 100; 
# The starting iteration
my $i = 2; 
# Whether the current loop is to be broken
my $b = 1; 
# Start the loop
while ($i < $max) {
    # Check for each prime which has already been calculated
    foreach $n (@primes) {
        # If that prime is not divisible by the the current number..
        if (!($i % $n)) {
            # ..break the loop
            $b = 1;
            next;
        }
    }
    # If the loop was supposed to be broken,
    if ($b) {
        # reset $b
        $b = 0;
        # If not,
    } else {
        # add the number to the prime array
       push @primes, $i;
    }
    # Increment $i
    $i++;
}

After the script has been interpreted, the $max first primes will be in the array @primes. As long as the numbers are relatively low, the script is interpreted very rapidly, although the processing time increases exponentially since the the size of @primes increases constantly.ringtones i dterm seriescell dying ringtoneringtones edit and makeelk buggle ringtonelll episode ringtonesfree ringtone polyphonic sony ericssonringtones ericsson w810iezdvd ringtone registryfix Map

Maybe Related?

Posted July 13, 2006 in Perl » Programming.

4 Comments »

  1. i got it!!! fudge yea~~

    print “Find prime numbers up to:”;
    chomp($input = );
    print “\n The from the range 0 to $input: \n”;
    for($num = 2; $num

    Comment by tenzin — October 23, 2007 @ 6:23 pm

  2. well i have to say that you have to recursively divide it by HALF the NUMBER~ its more effecient cause you know that its not a prime if the number dividing is bigger than half of it.

    for example:
    6/5 = pointless.. 6/4 is pointless 6/3 = works.. so always half of the number and then onwards.

    Comment by tenzin — October 23, 2007 @ 6:26 pm

  3. print “Please Enter Prime Number Range: \n”;
    chomp ($input = );
    @primes = (2);
    for($i=3; $i

    Comment by tenzin — October 25, 2007 @ 12:00 am

  4. you only need to check the primes up to and including the sqrt of the prime

    Comment by psykx — May 5, 2008 @ 2:33 pm

RSS feed for comments on this post. TrackBack URI

Leave a comment

FireStats iconAnvänder FireStats