# Prime Number Generator by Mark Holzrichter using a
# method invented in about 1984 by Mark.

# This has been checked against http://www.math.utah.edu/~alfeld/math/p10000.html
# upto 90089 which resulted from running this with:
# c:\oregon_sieve.pl 6 3 > output.txt

$num_primes_to_use = shift; # How many primes to use to build sieve
$extra_extend = shift;      # How much farther to extend sieve beyond primes used

# This will generate all the prime numbers up to a certain max number.
# This max number is the product of the first $num_primes_to_use primes 
# and $extra_extend.
# For example, $num_primes_to_use = 6, $extra_extend = 3.  The first 6 primes are
# 2 3 5 7 11 13, so max number is 2x3x5x7x11x13x3 = 90090.

$num_primes_to_use = 6 unless $num_primes_to_use;
$extra_extend = 3 unless $extra_extend;

@list = (1);
$product = 1;

sub output {
  if(length($line) + length($prime) > 78) {
    print "$line\n";
    $line = $prime;
  } else {
    $line = $line.' '.$prime;
  }
}

#$line .= '#Phase1:';

foreach (1..$num_primes_to_use) {
  $prime = $list[0] + 1;
  &output();
  $product = $product * $prime;
  @rawlist = (@list) x $prime; #very nice perl feature, does the magic!
  @list = ();
  $sum = 1;
  $save = 0;
  foreach $space (@rawlist) {
    $sum = ($sum + $space) % $prime;
    if($sum) {                 #do the sieve
      push @list,$space+$save;
      $save = 0;
    } else {
      $save = $save + $space;
    }
  }
}

#$line .= '#Phase2:';

@list = (@list) x $extra_extend;
$product = $product * $extra_extend;

while ((@list > 1) and ($prime*$prime <= $product)) {
  $prime = $list[0] + 1;
  &output();
  @rawlist = @list;            #don't grow list during 2nd phase
  @list = ();
  $sum = 1;
  $save = 0;
  foreach $space (@rawlist) {
    $sum = ($sum + $space) % $prime;
    if($sum) {                 #keep sifting in 2nd phase
      push @list,$space+$save;
      $save = 0;
    } else {
      $save = $save + $space;
    }
  }
}

#$line .= '#Phase3:';

$prime = 1;
foreach $space (@list) {
  $prime = $prime + $space;    #just list them in 3rd phase
  &output();
}
print "$line\n"; #list the last incomplete line