sub primes {
    my ($upto, $func) = @_;

    return large_primes($upto, $func) if $upto > 25000;
    $upto -= 1;
    my @flags = (1) x $upto;
    foreach my $i (0..$upto - 1){
        if ($flags[$i]){
            my $prime = $i + 2;
            my $k = $i + $prime;
            while($k < $upto){
                $flags[$k] = 0;
                $k += $prime;
            }
            $func->($prime);
        }
    }
}

sub large_primes {
    my ($upto, $func) = @_;

    # The Algorithm is adapted from http://w...content-available-to-author-only...k.com/~jrm/printprimes.html
    # This code is a translated version of Andreas Raab's #largePrimesUpTo:do: method
    # which was written for the Squeak Smalltalk environment.

    my $idx_limit = int(sqrt($upto)) + 1;
    my @flags = (0xFF) x (int(($upto + 2309) / 2310) * 60 + 60);
    my @primes_up_to_2310 = ();
    primes(2310, sub{ push(@primes_up_to_2310, $_[0]) });
    my @mask_bit_idx;
    $#mask_bit_idx = 2309;
    $mask_bit_idx[0] = 0;
    $mask_bit_idx[1] = 1;
    my $bit_idx = 1;
    foreach my $i (0..4){
        $func->($primes_up_to_2310[$i]);
    }
    my $idx = 5;
    foreach my $n (2..2309){
        $idx += 1 while $primes_up_to_2310[$idx] < $n;
        if( $n == $primes_up_to_2310[$idx] ){
            $mask_bit_idx[$n] = $bit_idx += 1;
        }
        elsif( $n % 2 == 0 || $n % 3 == 0 || $n % 5 == 0 || $n % 7 == 0 || $n % 11 == 0 ){
            $mask_bit_idx[$n] = 0;
        }
        else {
            $mask_bit_idx[$n] = $bit_idx += 1;
        }
    }
    for( my $n = 13; $n <= $upto; $n += 2 ){
        if( my $mask_bit = $mask_bit_idx[$n % 2310] ){
            my $byte_idx = int($n / 2310) * 60 + ($mask_bit - 1 >> 3);
            $bit_idx = 1 << ($mask_bit & 7);
            if( $flags[$byte_idx] & $bit_idx ){
                $func->($n);
                if( $n < $idx_limit ){
                    $idx = $n * $n;
                    $idx += $n if !($idx & 1);
                    while( $idx <= $upto ){
                        if( $mask_bit = $mask_bit_idx[$idx % 2310] ){
                            $byte_idx = int($idx / 2310) * 60 + ($mask_bit-1 >> 3);
                            $mask_bit = 255 - (1 << ($mask_bit & 7));
                            $flags[$byte_idx] = $flags[$byte_idx] & $mask_bit;
                        }
                        $idx += 2 * $n;
                    }
                }
            }
        }
    }
}

my $max = @ARGV == 1 ? $ARGV[0] : 100;
my $q = 0;
my $c = 0;
primes($max, sub{ $q = $_[0]; $c += 1; });
print $q, " ", $c, "\n";