Простое число [регулярное выражение]

/^1?$|^(11+?)\1+$/

Вот такое регулярное выражение послужит для определения простое число или нет. Применять его надо не к самому числу, а к строке, в которой столько единиц, сколько являет собой число. Если совпадений с регулярным выражением найдено не будет, то число простое. Так как в нем (рег. выражении) содержаться обратные ссылки, оно не будет работать на DFA-движке (для PHP — не будет работать в ereg, но будет работать в preg_).
С большими числами при стандартных настройках будут возникать проблемы. Будет даваться неверный результат. А все из-за того, что в PCRE установлен ограничительный параметр для количества обратных ссылок — pcre.backtrack_limit. Соответственно его и надо увеличить, что бы получить корректный результат (увеличивать надо в десятки раз для больших чисел).

Надеюсь, все понимают, что такой подход проверки простоты числа нельзя применять в реальной жизни из-за его чрезмерной ресурсоемкости и большом времени выполнения. Просто ознакомьтесь с ним и знайте, что он есть.

, , ,

Оставить комментарий

Top ↑ | Main page | Back