Первым делом отправим число, переданное в командной строке, в переменную $n:

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

Выводим, если нужно, двойку:

Perl
print "2\n" if $n>=2;

Теперь в цикле обрабатываются нечётные числа $i, начиная с 3:

Perl
for(my $i=3; $i<=$n; $i+=2)
{
	❶ вывести $i, если оно простое
}

Пришло время заняться вставкой ❶.

Цикл

Perl
for(my $j=3; $j<$i; $j+=2)
{
	if($i % $j==0)
	{
		last;
	}
}

проверяет $i на простоту. Обратите внимание, что перебираемые в нём возможные делители начинаются с тройки и все нечётные. И это правильно, так как у нечётных чисел $i не может быть чётных делителей $j. Первый же найденный делитель $j досрочно прерывает этот цикл. Но по окончании этого цикла невозможно определить, прервался ли он досрочно (то есть $i составное), или чаша была испита до дна (все потенциальные делители $j перебраны, но $i на них не делится). Поэтому после такого цикла нет информации, простое ли число $i и нужно ли его выводить.

Исправим ситуацию следующим образом. Непосредственно перед прерыванием цикла (last) опустим флаг в знак того, что число $i составное. Если цикл докрутится до конца, а флаг так и останется поднятым, значит, число простое. Естественно, флаг должен быть поднят в самом начале проверки числа $i. Это явление стоило бы назвать «презумпцией простоты»: число считается простым, если иное не будет доказано (предъявлен собственный делитель). По состоянию флага решается, выводится ли число:

Perl
my $flag=1;
for(my $j=3; $j<$i; $j+=2)
{
	if($i % $j==0)
	{
		$flag=0;
		last;
	}
}

print "$i\n" if $flag;

Этот код и следует вставить вместо ❶.

Эта весьма существенная оптимизация достанется нам малой ценой: нужно заменить заголовок цикла

Perl
for(my $j=3; $j<$i; $j+=2)

на

Perl
for(my $j=3; $j**2<=$i; $j+=2)

Взяв за основу программу, реализующую оптимизированный перебор делителей, внесём в неё некоторые изменения. Понадобится память для хранения найденных ранее простых чисел. В начале программы объявим массив @primes, уже содержащий двойку:

Perl
my @primes=(2);

Внешний цикл, в котором перебираются нечётные числа — кандидаты в простые, оснанется без изменений. Зато во внутреннем цикле на этот раз организуем перебор делителей среди элементов массива @primes. Поскольку по-прежнему нет нужды проверять делимость числа-кандидата на делители большие, чем квадратный корень из числа, оборвём цикл в нужный момент. В остальном тело внутреннего цикла останется тем же самым:

Perl
for my $j(@primes)
{
	last if $j**2>$i;
	…
}

Каждое найденное простое число не забываем добавлять в массив @primes:

Perl
if($flag)
{
	push @primes, $i;
	print "$i\n";
}

Взяв идею Эратосфена за основу, приступим к реализации программы на языке Perl.

Как и прежде, переменную $n предназначим для числа, вплоть до которого мы будем искать простые числа. Само решето разместим в массиве @sieve (sieve [sıv] — решето) длины $n-1$.

Каким образом реализовать зачёркивание? Будем просто обнулять то число, которое нужно зачеркнуть. Так мы, конечно, не узнаем, сколько раз число было зачёркнуто, но это и не требуется.

Особенностью нашего алгоритма будет то, что во время работы массив @sieve будет сокращаться: из его начала будут удаляться элементы, которые больше не представляют для нас интереса. Таким образом, память, занимаемая массивом, будет постепенно освобождаться, и к моменту завершения программы массив опустеет. Удаляться будут зачёркнутые (обнулённые) элементы, без всякого сожаления, но лишь те, которым не предшествует незачёркнутые. После этого первым в решете окажется незачёркнутое число $p$. Оно будет простым, его мы также удалим, запомнив в переменную $p. Это число мы выведем на экран, и используем для зачёркивания. После удаления $p$ первым в массиве (с нулевым индексом) окажется число $p+1$. Зачёркиванию подлежат числа $2p,3p,4p,\dots$, они теперь имеют индексы в массиве $p-1,2p-1,3p-1,\dots$.

Теперь пора подготовить решето. Можно, конечно, заполнить массив @sieve в цикле:

Perl
my @sieve;
for(my $i=2; $i<=$n; $n++)
{
	push @sieve, $i;
}

Однако ту же самую мысль можно выразить короче, используя оператор .. — конструктор списка:

Perl
my @sieve=2..$n;

Все дальнейшие действия заключаются в многократных проходах, при которых из массива @sieve удаляются составные числа (обнулённые), расположенные в самом начале массива, затем удаляется самый первый элемент, если он есть — это простое число. Оно запоминается в переменную $p, выводится на экран, и используется для дальнейшего вычёркивания (обнуления) каждого $p-го числа в массиве. Эти проходы делаются до тех пор, пока массив @sieve не опустеет:

Perl
while(@sieve)
{
	❷ удалить из начала массива @sieve нулевые элементы
	❸ удалить, запомнить в переменную $p, и вывести первый элемент массива @sieve
	❹ вычеркнуть (обнулить) каждый $p-й элемент массива, начиная с индекса $p-1
}

Поясним заголовок цикла while(@sieve). Как мы уже знаем, выражение-массив вычисляется по-разному в зависимости от того контекста, в котором оно встречается. Там, где ожидается массив (например, в аргументе команды shift), подставляется массив как таковой. Если же ожидается значение-скаляр, как, например, в выражении $i<@sieve, подставляется размер массива, а не сам массив. То же самое происходит в заголовке цикла, где проверяется условие: там ожидается скалярное логическое значение. Пока массив не пуст, его размер отличен от нуля, а ненулевые числа имеют значение «истина». Как только массив опустеет, выражение @sieve в заголовке цикла будет интерпретироваться как ложное, и следующий проход цикла не состоится.

Закодируем вставку ❷. Первая (неудачная) попытка могла быть такой:

Perl
while($sieve[0]==0)
{
	shift @sieve;
}

К сожалению, этот код приведёт при выполнении программы к потоку сообщений об ошибках — попытках обращения к неинициализированной переменной в числовом сравнении ==. Это происходит тогда, когда массив @sieve опустеет: в этом случае при очередной проверке условия цикла не удастся найти и сравнить с нулём первый элемент — его нет. Исправить ситуацию можно так:

Perl
while(@sieve and $sieve[0]==0)
{
	shift @sieve;
}

Этот код будет работать благодаря особенности вычисления логических выражений в языке Perl. Если массив @sieve пуст, левый операнд операции and будет интерпретироваться как ложное значение. Какое бы значение ни принял правый операнд, значение всего выражения всё равно будет ложным. В разных алгоритмических языках приняты разные сценарии вычислений подобных выражений — либо строгий (правый операнд всё равно вычисляется), либо экономный (правый операнд вычисляется только при необходимости). Иногда можно настроить поведение программы, выбрав сценарий. В Perl используется экономный сценарий, поэтому для пустого массива первый элемент не будет сравниваться с нулём. Если же массив не пуст, выражение @sieve слева от and будет истинным, и, значит, условие цикла будет иметь ту же истинность, что и правая часть выражения, поэтому эту правую часть придётся вычислять.

Экономный стиль вычислений касается также логической операции or: Если левый операнд имеет истинное значение, правый не вычисляется, так как значение выражения всё равно истинно независимо от значения правого операнда.

Примечание

Экономное вычисление логических значений в Perl имеет важные последствия: если с точки зрения логики выражения $x$ and $y$ и $y$ and $x$ эквивалентны, то с процедурной точки зрения это не так. От порядка операндов этой коммутативной (перестановочной) операции будет зависеть, в какой последовательности будут выполняться действия в программе, и будут ли они выполняться вообще. Особенную осторожность следует соблюдать, если выражения, расположенные слева и справа от операторов and и or, выполняют какие-то побочные действия: меняют значения переменных, осуществляют ввод/вывод, или могут привести к ошибке во время выполнения программы. Однако во многих ситуациях экономный стиль даёт удобства, в чём мы только что могли убедиться.

Переходим к вставке ❸. Поскольку после предшествующих манипуляций с массивом @sieve последний мог опустеть, имеет смысл в этом случае досрочно покинуть цикл:

Perl
last unless @sieve;

В противном случае удалим, запомним в переменной $p и выведем самый первый элемент массива — это простое число. Все эти действия умещаются в одной строке кода:

Perl
print my $p=shift @sieve, "\n";

Наконец, кодируем вставку ❹. Цикл совершенно очевиден:

Perl
for(my $i=$p-1; $i<@sieve; $i+=$p)
{
	$sieve[$i]=0;
}

Программа готова.

К недостаткам программы следует отнести тот факт, что во время её выполнения приходится держать в памяти большой список чисел (если $n велико). Хотя этот список постепенно сокращается, в начале работы он велик. Но это неизбежная плата за быстродействие. Вечная дилемма программиста — память или быстродействие — должна разрешаться по-разному в каждом конкретном случае. Возможна и такая ситуация, когда при не слишком больших $n больший расход памяти заметно ускорит программу, однако при очень больших $n существенно замедлит её работу или вообще воспрепятствует её выполнению из-за обращения к виртуальной (очень медленной) памяти или же полного исчерпания всей доступной памяти.

Определяем массив с первыми несколькими простыми числами и вычисляем их произведение:

Perl
my @primes=(2, 3, 5, 7);

my $wheelSize=1;
$wheelSize*=$_ for @primes;

Объявляем массив для колеса и заполняем его:

Perl
my @wheel;

outer: for my $s(2..$wheelSize+1)
{
	for my $p(@primes)
	{
		next outer unless $s % $p;
	}
	push @wheel, $s;
}

Обратите внимание на заголовок цикла: вместо for my $s(1..$wheelSize) мы написали for my $s(2..$wheelSize+1). Дело в том, что самая первая спица (это всегда единица) не годится в качестве делителя при проверке числа на простоту — единица не является собственным делителем. Так что заменив один заголовок цикла на другой, мы получаем повёрнутое колесо — вместо (1, 11, 13, 17, …, 199, 209) в колесе окажутся спицы (11, 13, 17, …, 199, 209, 211).

Теперь определяем процедуру isPrime, получающую число как параметр и возвращающую истинное значение для простых чисел, и ложное — для составных:

Perl
sub isPrime
{
	my $k=shift;
	for(@primes)
	{
		return 1 if $k==$_;
		return 0 unless $k % $_;
	}

	my @w=@wheel;
	while()
	{
		my $s=shift @w;
		return 1 if $s**2>$k;
		return 0 unless $k % $s;
		push @w, $s+$wheelSize;
	}
}

Первый цикл в теле процедуры пытается найти полученное число $k в массиве @primes, и в случае удачи, сразу же возвратить истинное значение. Иначе в цикле проверяется, не делится ли $k на очередное простое из массива @primes, и, если делится, возвращается ложь.

Если $k не совпадает ни с одним из первых простых чисел, ни делится ни на одно из них, $k проверяется на колесе, чему посвящён второй цикл.

Мы делаем локальную копию колеса @wheel в переменной @w, поскольку в дальнейшем при колёсной проверке колесо будет меняться (вращаться). Мы же не хотим, чтобы после завершения процедуры isPrime колесо @wheel осталось в изменённом состоянии.

Поворот колеса реализован в командах

Perl
my $s=shift @w;

и

Perl
push @w, $s+$wheelSize;

Первая команда извлекает (удаляет) из списка первую спицу, которая отправляется в переменную $s. Вторая добавляет в конец списка удалённую спицу, к номеру которой прибывляется длина окружности колеса. Тело цикла завершается двумя проверками: если очередное значение $s стало слишком большим, процедура констатирует, что собственный делитель не найден и не будет найден. Если число $k поделилось на очередное $s, оно объявляется составным.