О пользе чтения

amarovita · 18.09.2019 10:13
О пользе чтения

Попалась на кодеварс ката про числа Вильсона, легкая, сложность 8 (минимальная). Определить, является ли переданное число числом Вильсона, т. е. таким простым p, что p^2 делит (p-1)!+1:

(p-1)! \equiv -1 \pmod{p^2}

В общем, я долго что-то сочинял. Но не укладывался в ограничения по-времени. Потом не выдержал, пошел, почитал Википедию. Известно 3 числа Вильсона, 5, 13 и 563. Остальные, если и есть, находятся где-то далеко за 2\times10^{13}. А для проверки надо факториалы считать...

Вовремя читайте википедию!

def am_i_wilson(n):
    return n in (5, 13, 563)

Комментарии

Пока нет комментариев.

Войдите, чтобы комментировать.