Наши проекты:
Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту |
||
ПРАВИЛА | FAQ | Помощь | Поиск | Участники | Календарь | Избранное | RSS |
[3.17.184.90] |
|
Сообщ.
#1
,
|
|
|
Сегодня наткнулся на довольно старую задачку, имеющую очень простое решение, за использование которого в реальном коде нужно бить по рукам. Задачка такая:
С помощью какого регулярного выражения и как именно можно определить, что данное натуральное число является простым? Подсказка: регвыр не обязательно применять к самому числу. Просьба решение писать в спойлере. Тем, кому эта задача и ее решение уже известны, просьба не подсказывать. |
Сообщ.
#2
,
|
|
|
Четыре дня - и ни одного ответа. Задача слишком сложная? Или тривиальная и всем известная?
Может, еще подсказку? |
Сообщ.
#3
,
|
|
|
Если такой умный лучче подскажи регэксп, который из выражения находит первый символ который не [0-9] и возвращает выражение стоящее до этого символа
до Цитата 778899.abd112233 после Цитата 778899 |
Сообщ.
#4
,
|
|
|
Цитата AVA12 @ Просто влом Четыре дня - и ни одного ответа. Задача слишком сложная? Или тривиальная и всем известная? |
Сообщ.
#5
,
|
|
|
Mr. Gonarh, шутишь, да?
/^[0-9]*/ |
Сообщ.
#6
,
|
|
|
Нет, не шутил.
Добавлено Цитата fatalist @ Просто влом Добавлено +1 За подсказку |
Сообщ.
#7
,
|
|
|
Хорошо, подсказываю: для определения простоты используется метод пробного деления.
|
Сообщ.
#8
,
|
|
|
Мда. Печально. Вот решение:
Скрытый текст Есть целое неотрицательное число n, нужно с помощью регулярного выражения определить, является ли это число простым. Решение: Генерируем строку из n одинаковых непробельных символов. Затем проверяем эту строку выражением /^(?:.?|(..+?)\1+)$/ (для некоторых реализаций регвыров можно использовать более простое выражение). Тест вернет ложь для простых чисел и истину для прочих. Как это работает? Первая часть соответствует строкам длиной в 0 и 1 символ (числа 0 и 1 хоть не составные, но и не простые). Вторая часть захватывает в начале строки два символа и проверяет, можно ли уложить остаток строки захваченной подстрокой. Если это невозможно, то захватывается уже три символа и проверка повторяется, и т. д., пока не будет захвачена вся строка. Фактически, выражение проверяет, можно ли разбить строку на k одинаковых частей по m символов, где k, m >= 2. Если это возможно, то, очевидно, число n - составное, равное k*m (причем m - простое, так что заодно можно с помощью регвыров разложить число на простые множители). Если же невозможно, то n, очевидно, простое. Формулировку и разбор задачи можно посмотреть на stackoverflow. |