Как это регулярное выражение находит простые числа?
Возможный дубликат:
Как определить, является ли число простым с регулярным выражением?
На этой странице утверждается, что это регулярное выражение обнаруживает не простые числа (и контрпримером: простые числа):
/^1?$|^(11+?)\1+$/
Как это найти простые числа?
2 ответа
Я думаю, что статья объясняет это довольно хорошо, но я попробую свои силы в этом также.
Ввод в унарной форме. 1 является 12 является 113 является 111и т. д. Ноль - пустая строка.
Первая часть регулярного выражения соответствует 0 и 1 как непростая. Во-вторых, где волшебство начинает действовать.
(11+?) начинается с поиска делителей. Начинается с того, что определяется как 11или 2. \1 переменная, ссылающаяся на ранее записанное совпадение, поэтому \1+ определяет, делится ли число на этот делитель. (111111 начинается с присвоения переменной 11, а затем определяет, что оставшиеся 1111 является 11 повторяется, поэтому 6 делится на 2)
Если число не делится на два, механизм регулярных выражений увеличивает делитель. (11+?) становится 111и мы попробуем еще раз. Если в любой точке регулярное выражение совпадает, число имеет делитель, который не дает остатка, и поэтому число не может быть простым.
Мне потребовалась минута, чтобы понять, что это предназначено для чисел в base-1 (унарный?)
Несколько человек в этом обсуждении ycombinator объясняют это довольно хорошо. На самом деле эти объяснения более краткие, чем я думаю, что я могу получить, поэтому я оставлю это по ссылке.