Загадка , для извращенных умов

Сегодня наткнулся на довольно старую задачку, имеющую очень простое решение, за использование которого в реальном коде нужно бить по рукам. Задачка такая:

С помощью какого регулярного выражения и как именно можно определить, что данное натуральное число является простым? Подсказка: регвыр не обязательно применять к самому числу.

Просьба решение писать в спойлере. Тем, кому эта задача и ее решение уже известны, просьба не подсказывать.

Четыре дня - и ни одного ответа. Задача слишком сложная? Или тривиальная и всем известная?
Может, еще подсказку?

Если такой умный лучче подскажи регэксп, который из выражения находит первый символ который не [0-9] и возвращает выражение стоящее до этого символа
до

Цитата

778899.abd112233

после

Цитата

778899

Сообщение отредактировано: Mr. Gonarh - 07.11.12, 20:08

Цитата AVA12 @ 07.11.12, 18:20

Четыре дня - и ни одного ответа. Задача слишком сложная? Или тривиальная и всем известная?

Просто влом

Mr. Gonarh, шутишь, да?

/^[0-9]*/

Нет, не шутил.

Добавлено 08.11.12, 09:58

Цитата fatalist @ 08.11.12, 03:56

Просто влом

Добавлено 08.11.12, 09:58
+1 За подсказку

Хорошо, подсказываю: для определения простоты используется метод пробного деления.

Мда. Печально. Вот решение:

Скрытый текст

Есть целое неотрицательное число n, нужно с помощью регулярного выражения определить, является ли это число простым. Решение:

Генерируем строку из n одинаковых непробельных символов. Затем проверяем эту строку выражением /^(?:.?|(..+?)\1+)$/ (для некоторых реализаций регвыров можно использовать более простое выражение). Тест вернет ложь для простых чисел и истину для прочих.

Как это работает? Первая часть соответствует строкам длиной в 0 и 1 символ (числа 0 и 1 хоть не составные, но и не простые). Вторая часть захватывает в начале строки два символа и проверяет, можно ли уложить остаток строки захваченной подстрокой. Если это невозможно, то захватывается уже три символа и проверка повторяется, и т. д., пока не будет захвачена вся строка. Фактически, выражение проверяет, можно ли разбить строку на k одинаковых частей по m символов, где k, m >= 2. Если это возможно, то, очевидно, число n - составное, равное k*m (причем m - простое, так что заодно можно с помощью регвыров разложить число на простые множители). Если же невозможно, то n, очевидно, простое.

Формулировку и разбор задачи можно посмотреть на stackoverflow.

Сообщение отредактировано: AVA12 - 10.11.12, 16:58