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

####
print '
use strict;
use warnings;

use Benchmark qw{ cmpthese };

sub primes_original {
    my $n = shift;
    return if $n < 2;

    my @primes = (2);
    for my $i (3 .. $n) {
        my $sqrt = sqrt $i;
        my $notprime;
        for my $p (@primes) {
            last if $p > $sqrt;

            $notprime = 1, last if 0 == $i % $p;
        }
        push @primes, $i unless $notprime;
    }
    return @primes
}
';

my @givenp = qw(2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149);

foreach my $num (0..$#givenp){
####
print '

sub primes_opt_till_'.$givenp[$num].' {
    my $n = shift;
    return if $n < 2;

    my @primes = (2);
    for my $i (3 .. $n) {
';
foreach my $quot ( 0 .. $num ){
####
print "\t\t\t\t".'if($i%'.$givenp[$quot].'==0){next}'."\n";
}
####
print '
        my $sqrt = sqrt $i;
        my $notprime;
        for my $p (@primes) {
            last if $p > $sqrt;

            $notprime = 1, last if 0 == $i % $p;
        }
        push @primes, $i unless $notprime;
    }
    return @primes
}
##

';
}

####
print '
cmpthese(-10,
        {
primes_original => \'primes_original (10000)\',
';
foreach my $num (0..$#givenp){
    print "opt_till_$givenp[$num] => 'primes_opt_till_$givenp[$num] (10000)',\n";
}
####
print'
        });
';