Идеи реализации

Будем считать, что число k, которое необходимо проверить на простоту, содержится в переменной $_.

Число k будет составным тогда и только тогда, когда его можно представить в виде суммы не менее двух одинаковых слагаемых, каждое из которых не меньше двух. Возможность такого разбиения означает возможность представить число k в виде произведения x y , где x — количество слагаемых в сумме, а y — величина этих равных между собой слагаемых.

Сформируем строку, которая состоит из $_ одинаковых символов. Для нас будет совершенно неважно, какие именно символы будут использованы, пусть для определённости это будут буквы Q. Оказывается, можно проверить, является ли число $n составным, сопоставив такую строку с некоторым регулярным выражением.

Если символы в такой строке удастся разделить на несколько одинаковых групп, состоящих как минимум из двух символов, тогда длина строки окажется составным числом.

Группа, включающая не меньше двух символов, описывается шаблоном Q{2,}, или, короче, QQ+. Вся строка, от начала до конца, должна состоять как минимум из двух групп.

Возникает соблазн сопоставить строку с регулярным выражением ^(QQ+){2,}$, но это ошибка. В таком регулярном выражении не отражён тот факт, что группы должны быть одинаковыми. Сопоставление с данным регулярным выражением ответит на вопрос, можно ли представить данное число k в виду суммы нескольких слагаемых, бо́льших 2, но необязательно равных между собой.

Правильное регулярное выражение будет таким: ^(QQ+)\1+$. Оно требует, чтобы строка состояла из группы, за которой следует как минимум одна точно такая же группа.

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