#!/usr/bin/env perl

# Eratosthenes' screen, returns prime numbers smaller than given positive
# integer.

use strict;
use warnings;
use Set; # My own integer set class

print "Enter a natural number greater than 1: ";
chomp(my $n = <STDIN>);

my $set = screen($n);

print "Prime numbers smaller or equal than $n are: " . $set->to_string(). "\n";

sub screen {
  my $n = shift;

  die "There are no primes smaller or than equal than $n\n" if ($n < 2);

  my @s = ( 2..$n );
  my $s = Set->new( 2..$n );
  my $a = Set->new();
  my $b;
  
  my $r = 1;
  do {
    $b = $s->min();
    $a->union($b);
    my $m = $b;
    
    do {
      $s->remove($m);
      $m = $m + $b;
      $r++;
    } until ($m > $n);
  } until ($b > sqrt($n));
  
  $a->union($s);

  return $a;
}