Готовая программа (предварительная версия)

#!/usr/bin/perl

use warnings;
use BitSetSimple;

my $n=shift or die "Укажите число в командной строке\n";

my $sieve=BitSetSimple->new;
for(my $i=2; $i<=$n; $i++)
{
	$sieve->add($i);
}

for(my $p=2; $p<=$n; $p++)
{
	while(not $sieve->isMember($p) and $p<=$n)
	{
		$p++;
	}
	last if $p>$n;
	print "$p\n";
	for($i=2*$p; $i<=$n; $i+=$p)
	{
		$sieve->delete($i);
	}
}
package BitSetSimple;

sub new()
{
	my $class=shift;
	my $string='';
	return bless \$string, $class; 
}

sub get($)
{
	my $self=shift;
	my $i=shift;
	return 0 if length $$self<=int($i/8);
	return ord(substr $$self, int($i/8), 1)&(1<<($i % 8));
}

sub set($$)
{
	my $self=shift;
	my $i=shift;
	my $value=shift;
	while(length $$self<=int($i/8))
	{
		$$self.="\0";
	}
	my $byte=ord substr $$self, int($i/8), 1;
	if($value)
	{
		$byte|=(1<<($i % 8));
	}
	else
	{
		$byte&=~(1<<($i % 8));
	}
	substr $$self, int($i/8), 1, chr $byte;
	while(length $$self and (substr $$self, -1) eq "\0")
	{
		chop $$self;
	}
}

sub isMember($)
{
	return shift->get(shift);
}

sub add($)
{
	shift->set(shift, 1);
}

sub delete($)
{
	shift->set(shift, 0);
}

sub toString()
{
	my $self=shift;
	my $string='';
	for(my $i=0; $i<8*length $$self; $i++)
	{
		$string.="$i," if $self->get($i);
	}
	chop $string if (substr $string, -1) eq ',';
	return "{$string}";
}

return 1;
Информатика-54© А. Н. Швец