Finding prime numbers - Perl

In the last article, I talked about the need to work at the bit level in Perl and in other languages. In order to understand bits, we first took a look at how binary numbers are represented in Perl, and then we took a look at two bitwise operators, AND and OR. In looking at the operators, we looked at their most common uses in programming. We also began to look at an algorithm for finding prime numbers, but we stopped upon seeing that there is no easy implementation, at least not without a knowledge of bits.

TABLE OF CONTENTS:

By: Peyton McCullough

Poor Best

Rating:

/ 1

September 14, 2009

print this article

SEARCH DEV SHED

TOOLS YOU CAN USE

We now have everything we need to implement the algorithm, so let's get to it. The first thing we need to do is create a bit vector that contains a bit for all of the values up to a maximum. Let's find the first one million prime numbers:

use constant MAX => 1_000_000;

In order to create the bit vector, we can use the vec function and an empty string. The vec function, if you pass it an index outside of the string, will simply fill all of the missing elements with zeros. So, we can easily create a vector with one million elements like this:

my $sieve = '';

vec($sieve, MAX, 1) = 0;

However, all of the elements are zero, which means that all of them are initially marked as not prime. We want all of them to start as prime, and then eliminate non primes from this list. So, let's flip all of the bits:

$sieve = ~$sieve;

(We could assume that 0 means prime and save ourselves an operation, but that's probably a bit less intuitive).

Now we have a bit vector to use, and we can begin to apply the algorithm. The algorithm is simple. We just need to find the first unexamined prime number (2 to start with) and then eliminate its multiples. We then repeat this until we have reached the square root of the maximum number (which would be 1,000). Here's the code:

for (my $i = 2; $i <= sqrt(MAX); $i++) {

next unless (vec($sieve, $i, 1));

for (my $x = $i * 2; $x <= MAX; $x += $i) {

vec($sieve, $x, 1) = 0;

}

As you can see, we loop over the numbers 2 through 1,000. If the number is known to be not prime (that is, if the bit value is 0), then we move on to the next number. Otherwise, we mark its multiples as not prime by setting their corresponding bits to 0.

That's it! We're done! We can now print the results:

for (2..MAX) {

print "$_n" if (vec $sieve, $_, 1);

}

Here's the full code:

#!/usr/bin/perl

use strict;

use warnings;