Как всегда, отправим параметр командной строки в переменную $n:

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

Перебирая в цикле натуральные числа от 2 до $n, будем выводить те из них, которые окажутся простыми:

Perl
for(2..$n)
{
	print "$_" if ('Q' x $n)!=m/^(QQ+)\1+$/;
}

Мы получаем вполне работоспособную программу, которую, впрочем, можно улучшить. Прежде всего заметим, что такие трудоёмкие действия, как создание строки 'Q' x $n и, особенно, её сопоставление с регулярным выражением, производятся для всех без исключения чисел из списка, в то время как кандидатами в простые числа являются лишь нечётные и двойка. Проверить число на нечётность будет гораздо быстрее, чем применять описанный метод проверки на простоту: выражение $_ % 2 истинно лишь для нечётных $_ (для чётных $_ этот остаток от деления на два равен нулю, что означает ложь). Это наблюдение позволяет заменить выражение, осуществляющее проверку простоты на такое: $_ % 2 and ('Q' x $n)!=m/^(QQ+)\1+$/. Чтобы не упустить двойку, добавим дополнительное условие: $_ % 2 and ('Q' x $n)!=m/^(QQ+)\1+$/ or $_==2.

По сути эти добавления ничего не меняют: утверждение «число простое» равносильно утверждению «число нечётное и простое или оно равно двум». Однако вспомним про ленивое вычисление логических выражений в Perl. Целью улучшений было стремление исключить трудоёмкую проверку простоты для чётных чисел. И это получилось: если число чётное, проверка на простоту для него не будет производиться. В этом случае нужно лишь проверить, не является ли такое чётное число двойкой, поскольку лишь это условие может повлиять на значение всего логического выражения. Если же число нечётно, оно будет проверено на простоту (тут уж никуда не денешься), но если оно окажется простым, сравниваться с двойкой оно не будет. Конечно же, обмен местами выражений, окружающих оператор and, сведёт на нет всю эту нашу маленькую хитрость.

Хитрость эта действительно маленькая, поскольку не даст ожидаемого двукратного ускорения работы программы. Мы провели эксперимент и убедились, что упрощённая обработка чётных чисел экономит около $6\%$ времени исполнения программы при $n=10000$, и около $5\%$ при $n=20000$. Дело в том, что сопоставление строки с регулярным выражением в случае чётного числа пройдёт успешно и сравнительно быстро — первое же найденное разбиение строки на группы приведёт к немедленному завершению сопоставления. Другое дело в нечётном случае. Механизм, осуществляющий сопоставление, переберёт группы всевозможной длины, пока не обнаружит, что строка не подходит к регулярному выражению.

У нас в запасе имеется ещё одна хитрость, и на этот раз большая.

Посмотрим на шаблон для группы символов: (QQ+). При сопоставлении строки с нашим регулярным выражением этот шаблон, в силу своей природной прожорливости, «съест» всю строку, поскольку вся строка ему соответствует. После этого будет сделана попытка отыскать в оставшейся, «несъеденной» части строки (естественно, эта часть окажется пустой) ещё как минимум одну копию группы. Эта попытка, конечно, обречена. Тогда предпринимается ещё одна попытка, при которой группа съедает все символы строки, кроме последнего. Снова неудача. Придётся при следующем захвате в группу отдать ещё один символ. Вспомним, что длина строки, захваченной в группу — это один из делителей числа $n$. Получается, что потенциальные делители перебираются в порядке убывания, начиная с $n$. Однако, как нам известно, у составного числа собственный делитель не может превышать $\sqrt{n}$. Лучше перебирать кандидатов делители в возрастающем порядке — тогда мы скорее обнаружим делитель. В нашем алгоритме можно этого добиться, подавив прожорливость шаблона, с помощью которого происходит захват в группу: (QQ+?).

Эта находка приводит к экономии при $n=10000$ в $\mathrm{28,5}\%$ (а вместе с маленькой хитростью $\mathrm{34,3}\%$), а при $n=20000$ в $\mathrm{39,6}\%$ (соответственно $\mathrm{44,2}\%$) времени исполнения программы. Так говорит эксперимент.