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;
use constant MAX => 1_000_000;
my $sieve = ''; vec($sieve, MAX, 1) = 0; $sieve = ~$sieve;
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; } }
for (2..MAX) { print "$_n" if (vec $sieve, $_, 1); }
There is, of course, a lot more to using bits that cannot possibly be explained in the space provided by two articles. Even the things I have explained here can be elaborated on significantly, and some of the things I've left out are actually pretty important. But even so, you should now have a basic knowledge of bits, along with, hopefully, an appreciation of them. Good luck!
blog comments powered by Disqus 






