primes2.pl, a slower primes sieve

primes2.pl

# primes2.pl by kernigh
#
# This solves https://github.com/PlummersSoftwareLLC/Primes in Perl
# using a vec string.  It is slower than solution_1/primes.pl which
# uses an array: 7 iterations for primes2.pl versus 13 iterations for
# solution_1 on the same cpu.
#
# This primes2.pl is a translation from PrimeCPP.cpp, but without the
# count_primes method, and is "under BSD-new/BSD-3 or a more
# permissive license" (quoting CONTRIBUTING.md).

use strict;
use warnings;
use Time::HiRes qw(time);

package PrimeSieve;

sub new {
  my ($class, $n) = @_;

  # The bits are 0s (prime); the sieve will put 1s (not prime).
  my $bits = "";
  vec($bits, $n, 1) = 0;

  bless {bits => $bits, sieve_size => $n}, $class
}

sub run_sieve {
  my ($self) = @_;
  my $sieve_size = $self->{sieve_size};
  my ($factor, $num, $q, $twice_factor);

  # The alias $bits avoids fetching $self->{bits} more than once.
  for my $bits ($self->{bits}) {
    $factor = 3;
    $q = sqrt($sieve_size);
    while ($factor <= $q) {
      unless (vec($bits, $factor, 1)) {
        # $factor is prime, its multiples are not prime.
        $num = $factor * $factor;
        $twice_factor = 2 * $factor;
        while ($num <= $sieve_size) {
          vec($bits, $num, 1) = 1;
          $num += $twice_factor;
        }
      }
      $factor += 2;
    }
  }
}

sub print_results {
  my ($self, $show_results, $duration, $passes) = @_;

  if ($show_results) {
    my ($bits, $sieve_size) = ($self->{bits}, $self->{sieve_size});
    print "2, " if 2 <= $sieve_size;
    for (my $num = 3; $num <= $sieve_size; $num += 2) {
      print "$num, " unless vec($bits, $num, 1);
    }
    print "\n";
  }

  print "kernigh;$passes;$duration;1\n"
}

package main;

my $passes = 0;
my $t_start = time;
my $duration;
while (1) {
  my $sieve = PrimeSieve->new(1_000_000);
  $sieve->run_sieve;
  $passes++;
  if (($duration = time - $t_start) >= 5) {
    $sieve->print_results(0, $duration, $passes);
    last;
  }
}