Будем считать, что число , которое
необходимо проверить на простоту, содержится в переменной
$_
.
Число будет составным тогда и только тогда, когда его можно представить в виде суммы не менее двух одинаковых слагаемых, каждое из которых не меньше двух. Возможность такого разбиения означает возможность представить число в виде произведения , где — количество слагаемых в сумме, а — величина этих равных между собой слагаемых.
Сформируем строку, которая состоит из $_
одинаковых
символов. Для нас будет совершенно неважно, какие именно символы будут
использованы, пусть для определённости это будут буквы Q
.
Оказывается, можно проверить, является ли число $n
составным, сопоставив такую строку с некоторым регулярным выражением.
Если символы в такой строке удастся разделить на несколько одинаковых групп, состоящих как минимум из двух символов, тогда длина строки окажется составным числом.
Группа, включающая не меньше двух символов, описывается шаблоном
Q{2,}
, или, короче, QQ+
. Вся строка,
от начала до конца, должна состоять как минимум из двух групп.
Возникает соблазн сопоставить строку с регулярным выражением
^(QQ+){2,}$
, но это ошибка. В таком регулярном выражении не
отражён тот факт, что группы должны быть одинаковыми.
Сопоставление с данным регулярным выражением ответит на вопрос, можно ли
представить данное число в виду
суммы нескольких слагаемых, бо́льших ,
но необязательно равных между собой.
Правильное регулярное выражение будет таким: ^(QQ+)\1+$
.
Оно требует, чтобы строка состояла из группы, за которой следует как минимум
одна точно такая же группа.