#!/usr/bin/perl
use strict;
use warnings;

use constant error            => -1;
use constant noerror          => 0;
use constant false            => 0;
use constant true             => 1;

$| = true;

#
# Modules Used
#
use Data::Dumper::Simple;
use DEM::Print;
use Time::HiRes qw( gettimeofday tv_interval );

#
# PrintPrimes
#
# Print Primes in a line, wrap at $column
#
# Arguments: $Primes - Array of Primes
#            $WrapAt - Column to wrap at
#
# Returns: $PrimeString - Comma seperated list of primes Found
#
sub PrintPrimes
{
   my($Primes, $WrapAt, $Iterations) = @_;

   my $PrimeString = '';
   my $PrimeStrings;
   my $ItLength = length($Iterations);

   foreach my $Prime (@$Primes)
      {
      my $PreviousPrimeString = $PrimeString . "\n";
      $PrimeString .= sprintf("%*.0d", $ItLength, $Prime) . ', ';
      if(length($PrimeString) > $WrapAt)
         {
         push(@$PrimeStrings, $PreviousPrimeString);
         $PrimeString = $Prime . ', ';
         }
      }

   chop($PrimeString);
   $PrimeString .= "\n\n";
   push(@$PrimeStrings, $PrimeString);
   $PrimeString = '';

   foreach my $String (@$PrimeStrings)
      {
      $PrimeString .= $String;
      }

   return($PrimeString);
}

#
# Classic
#
# Classic Sieve of Eratosthenes
#
# Arguments: $n - Number of Iterations
#
# Returns: @Primes - List of Primes Found
#
sub Classic
{
   my $n = shift;
   my @composite;
   for my $i (2 .. int(sqrt($n)))
      {
      if (!$composite[$i])
         {
         for (my $j = $i*$i; $j <= $n; $j += $i)
            {
            $composite[$j] = 1;
            }
         }
   }
   my @primes;
   for my $i (2 .. $n)
      {
      $composite[$i] || push @primes, $i;
      }
   @primes;
}

#
# OddsOnly
#
# Odds Only a Faster Sieve
#
# Arguments: $n - Number of Iterations
#
# Returns: @Primes - List of Primes Found
#
sub OddsOnly
{
  my($n) = @_;
  return @{([],[],[2],[2,3],[2,3])[$n]} if $n <= 4;

  my @composite;
  for (my $t = 3;  $t*$t <= $n;  $t += 2)
     {
     if (!$composite[$t])
        {
        for (my $s = $t*$t;  $s <= $n;  $s += $t*2)
           {
           { $composite[$s]++ }
           }
     }
  }

  my @primes = (2);
  for (my $t = 3;  $t <= $n;  $t += 2)
     {
     $composite[$t] || push @primes, $t;
     }

  @primes;
}

#
# OddsOnlyVectors
#
# Odds Only a Faster Sieve With Vectors
#
# Arguments: $end - Number of Iterations
#
# Returns: @Primes - List of Primes Found
#
sub OddsOnlyVectors
{
  my($end) = @_;
  return @{([],[],[2],[2,3],[2,3])[$end]} if $end <= 4;
  $end-- if ($end & 1) == 0; # Ensure end is odd

  my ($sieve, $n, $limit, $s_end) = ( '', 3, int(sqrt($end)), $end >> 
+1 );
  while ( $n <= $limit ) {
    for (my $s = ($n*$n) >> 1; $s <= $s_end; $s += $n) {
      vec($sieve, $s, 1) = 1;
    }
    do { $n += 2 } while vec($sieve, $n >> 1, 1) != 0;
  }
  my @primes = (2);
  do { push @primes, 2*$_+1 if !vec($sieve,$_,1) } for (1..int(($end-1
+)/2));
  @primes;
}

#
# OddsOnlyStrings
#
# Odds Only With Strings
#
# Arguments: $end - Number of Iterations
#
# Returns: @Primes - List of Primes Found
#
sub OddsOnlyStrings
{
  my($end) = @_;
  return @{([],[],[2],[2,3],[2,3])[$end]} if $end <= 4;
  $end-- if ($end & 1) == 0;
  my $s_end = $end >> 1;

  my $whole = int( ($end>>1) / 15);    # prefill with 3 and 5 marked
  my $sieve = '100010010010110' . '011010010010110' x $whole;
  substr($sieve, ($end>>1)+1) = '';
  my ($n, $limit, $s) = ( 7, int(sqrt($end)), 0 );
  while ( $n <= $limit ) {
    for ($s = ($n*$n) >> 1; $s <= $s_end; $s += $n) {
      substr($sieve, $s, 1) = '1';
    }
    do { $n += 2 } while substr($sieve, $n>>1, 1);
  }
  # If you just want the count, it's very fast:
  #       my $count = 1 + $sieve =~ tr/0//;
  my @primes = (2, 3, 5);
  ($s, $n) = (3, 7-2);
  while ( (my $nexts = 1 + index($sieve, "0", $s)) > 0 ) {
    $n += 2 * ($nexts - $s);
    $s = $nexts;
    push @primes, $n;
  }
  @primes;
}

#
# SieveIt
#
# Run all the Sieve Routines
#
# Arguments: $end - Number of Iterations
#
# Returns: Not Much
#
sub SieveIt
{
   my ($Iterations, $Sieves) = @_;

   #
   # Run each Sieve of Eratosthenes routine
   #
   foreach my $Sieve (keys(%$Sieves))
      {
      my $StartingTime = [gettimeofday()];
      my @Primes = $Sieves->{$Sieve}->{'Sub'}->($Iterations);
      my $ElapsedTime = tv_interval($StartingTime);
      $Sieves->{$Sieve}->{'Time'} = $ElapsedTime;
      Print(sprintf("%s:%.6f\n", $Sieve, $ElapsedTime) . PrintPrimes(\
+@Primes, 80, $Iterations));
      }

   Print("Times:\n");
   foreach my $Sieve (sort({$Sieves->{$a}->{'Time'} <=> $Sieves->{$b}-
+>{'Time'}} keys(%$Sieves)))
      {
      Print(sprintf("%16s:%.6f\n", $Sieve, $Sieves->{$Sieve}->{'Time'}
+));
      }
}

#
# Main
#
if($ARGV[0] !~ /^\d+$/)
   {
   Print("Usage: Sieve NumberOfIterations\n");
   exit(1);
   }

my $Sieves;
%$Sieves =
   (
     'Classic' =>
         {
           'Sub'  => \&Classic
         , 'Time' => 0
         }
   ,
     'OddsOnly' =>
         {
           'Sub'  => \&OddsOnly
         , 'Time' => 0
         }
   ,
   'OddsOnlyVectors' =>
       {
         'Sub'  => \&OddsOnlyVectors
       , 'Time' => 0
       }
 ,
   'OddsOnlyStrings' =>
       {
         'Sub'  => \&OddsOnlyStrings
       , 'Time' => 0
       }
 ,
   )
;

SieveIt($ARGV[0], $Sieves);
__END__
[download]