Skip to content

Instantly share code, notes, and snippets.

@BenGoldberg1
Last active November 22, 2015 15:34
Show Gist options
  • Save BenGoldberg1/9f8b188f8654003acb3b to your computer and use it in GitHub Desktop.
Save BenGoldberg1/9f8b188f8654003acb3b to your computer and use it in GitHub Desktop.
Yet another Primes thingy
#!perl
use strict;
use warnings;
package primes;
sub new { bless [2, 3], shift }
sub next {
my ($self) = @_;
bless $self, 'primes0' if @$self == 1;
shift @$self;
}
package primes0;
sub next {
my ($self) = @_;
@$self = ( [], [(undef) x 3] );
for( 3, 9, 3 ) {
my $tmp = $_;
push @$self, \$tmp;
}
bless $self, 'primes1';
goto &primes1::next;
}
package primes1;
use vars qw, @primes @sieve $p $q $n ,;
sub next {
my ($self) = @_;
local (*primes, *sieve, *p, *q, *n) = @$self;
my ($primes_used, $c_offset) = (0, 0);
for my $a_factor (@sieve) {
$n += 2;
if ($a_factor) {
my $d = $a_factor;
$d += $a_factor while $sieve[ $c_offset + $d ];
$sieve[ $c_offset + $d ] = $a_factor;
} elsif ( $n < $q ) {
splice @sieve, 0, $c_offset+1;
splice @primes, 0, $primes_used;
push @primes, $n;
return $n;
} else {
my $d = $p;
$d += $p while $sieve[ $c_offset + $d ];
$sieve[ $c_offset + $d ] = $p;
$p = $primes[ $primes_used++ ];
$q = $p * $p;
}
++$c_offset;
}
die "Shouldn't get here!";
}
package main;
my $p = primes->new;
for( 1..100 ) {
print $p->next, " ";
}
print "\n";
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment