$ time perl -w
use strict;
my $UPPER = 1_000_000;
my $sieve = "";
GUESS: for (my $guess = 2; $guess <= $UPPER; $guess++) {
  next GUESS if vec($sieve,$guess,1);
  #print "$guess\n";
  for (my $mults = $guess * $guess; $mults <= $UPPER; $mults += $guess
+) {
    vec($sieve,$mults,1) = 1;
  }
}
__END__

real    0m10.003s
user    0m2.191s
sys     0m0.003s
[download]

See also Math::Prime::XS.

It includes clever use of the vec operator.

Maybe there's historical reasons for using vec over substr, but nowadays it's much faster to use substr. The for my $foo ($from .. $to) { ... } construct is also slightly more efficiently than for (my $foo = $from; $foo <= $to; $foo++) { ... }. My guess is that the C-style loop was used as the "range loop" wasn't optimized back then and actually generated a list of, in this case, a million numbers.

I changed the for loop and did a direct translation to using substr instead of vec, and here's the results:

Benchmark: running substr, vec for at least 60 CPU seconds...
    substr: 61 wallclock secs (62.41 usr +  0.02 sys = 62.42 CPU) @  1
+.09/s (n=68)
       vec: 58 wallclock secs (60.64 usr +  0.02 sys = 60.66 CPU) @  0
+.73/s (n=44)
       s/iter    vec substr
vec      1.38     --   -33%
substr  0.918    50%     --
[download]

Here's the code:

use strict;
use warnings;
use Benchmark qw(cmpthese timethese);

my %subs;

######################################################################
+#########

my $UPPER = 1_000_000;

$subs{vec} = sub {
    my $sieve = "";
    GUESS: for my $guess (2 .. $UPPER) {
        next GUESS if vec($sieve,$guess,1);
        #print "$guess\n";
        for (my $mults = $guess * $guess; $mults <= $UPPER; $mults += 
+$guess) {
            vec($sieve,$mults,1) = 1;
        }
    }
};

$subs{substr} = sub {
    my $sieve = '0' x ($UPPER + 1);
    GUESS: for my $guess (2 .. $UPPER) {
        next GUESS if substr($sieve,$guess,1);
        #print "$guess\n";
        for (my $mults = $guess * $guess; $mults <= $UPPER; $mults += 
+$guess) {
            substr($sieve,$mults,1,1);
        }
    }
};

######################################################################
+#########

cmpthese(timethese(-60, \%subs));
[download]

lodin

The main advamtage of vec over substr is going 8 x higher for any given amount of ram.

Of course, you can go twice as high and a little quicker, with either, by not wasting space for even numbers.

And once you start saving space, you can go as far as 8 bits for every 30 numbers and higher still.

---

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.

"Science is about questioning the status quo. Questioning authority".

In the absence of evidence, opinion is indistinguishable from prejudice.

"Too many [] have been sedated by an oppressive environment of political correctness and risk aversion."

nowadays it's much faster to use substr

I re-ran your benchmark on Linux 2.6.9 i686, perl v5.8.5 built for i386-linux-thread-multi. The difference was much less than what you encountered.

$ perl -w 666965.pl
Benchmark: running substr, vec for at least 60 CPU seconds...
    substr: 67 wallclock secs (60.69 usr +  0.03 sys = 60.72 CPU) @  0
+.58/s (n=35)
       vec: 66 wallclock secs (61.33 usr +  0.04 sys = 61.37 CPU) @  0
+.54/s (n=33)
       s/iter    vec substr
vec      1.86     --    -7%
substr   1.73     7%     --
[download]

On Linux 2.6.22-10-386 i686, perl v5.10.0 (different hardware than above):

Benchmark: running substr, vec for at least 60 CPU seconds...
    substr: 62 wallclock secs (61.69 usr +  0.05 sys = 61.74 CPU) @  0
+.44/s (n=27)
       vec: 61 wallclock secs (60.81 usr +  0.05 sys = 60.86 CPU) @  0
+.39/s (n=24)
       s/iter    vec substr
vec      2.54     --   -10%
substr   2.29    11%     --
[download]

Update Mon Feb 11 12:13:38 CET 2008: Added perl 5.10 benchmark on lodin's request.
--
Andreas

See Abigail one-liners here

#Abigail
perl -wle 'print "Prime" if (1 x shift) !~ /^1?$|^(11+?)\1+$/'
%%
#Abigail
perl -wle 'print "Prime" if (0 x shift) !~ m 0^\0?$|^(\0\0+?)\1+$0'
%%
#Abigail
perl -wle 'print "Prime" if ("m" x shift) !~ m m^\m?$|^(\m\m+?)\1+$mm'
[download]

perl -wle 'print "Prime" if (1 x shift) !~ /^1?$|^(11+?)\1+$/'

OK so I thought i'd elaborate a little on how this works since the monks from the chatterbox took time to explain it to me :)

So you have a number, say 6, and "write" it as a sequence of 1 ie (111111) .
If you write it (11)(11)(11) "you just found that 6 = 3 * 2", as moritz explained it.

ELISHEVA explains the math behind this :
if there is a repeating group of the same number of ones, then a factorization is possible and hence the number can't be prime.

It means that if you can write the number as M groups of K ones, then it factorizes as :

M * [ Sum(p=1->k) 1 ] which really is just M * K

Which means that our number can be divided by M (or K), and therefore it's not prime. Shmem gives an example: i.e. for m = 1763, the group found would be 11111111111111111111111111111111111111111 repeated 43 times - not prime

So how does the regexp implement that ? We can decompose it like this :

m/
   ^                  # start of line
     1?               # the number 1, zero or one time
   $                  # end of line
 
   |                  # alternation
 
   ^                  # start of line
     (                # remember the match in \1 
       11+?           # the number 1, then the number 1 once or more t
+imes, but the less time possible
     )                # 
     \1+              # the matched sequence, once or more.
   $
/x ;
[download]

So the real trick is in (11+?). In a standalone context, it will only match 11. That's because +? means "once or more but the minimum number of times". On the other hand, ^(11+?)$ will match a whole sequence of ones from begining to end.

Here (11+?) is followed by \1+$ which means : itself, once or more, until the end of the line .
So what happens is that the "minimum number of times" that's contained in +? is seen from the \1+$ that is after it in the expression
So when no match occurs, the engine will go back to the (11+?) and try again.

I understand that's what backtracking is. Eventually the regexp engine will try every grouping of ones and fine none.
Since it needs at least two groupings to match (enforced by the + in \1+ ), a prime number will not match.

The only problem is that for some numbers you get a Complex regular subexpression recursion limit (32766) exceeded error. My guess was that it happens when the engine has to try more than 32766 number of times, ie the first fail appears for a number that needs K>32766. That's not the case though, since prime number 32779 does not yield the error. 65558 does, though. I went on and brutforced it, to find that the error appears first with 65536, which is 2 * 32768, which computes since it needs two groups to match...

It is difficult to comment without knowing what the function is supposed to do. As far as I can tell it prints out all the numbers less than 1,000 that are not divisible by 2, 3, 5 or 7.

Now just for fun

use 5.010_000;

say for grep { ( $_ % 2 && $_ % 3 && $_ % 5 && $_ % 7 ) } 2 .. 1_000;
[download]

And the question is?