Пост Проверить, является ли число n простым, можно детерминированно и за полиномиальное время всего в 10 строках Python.

Проверить, является ли число n простым, можно детерминированно и за полиномиальное время всего в 10 строках Python. Этот алгоритм предложил Гэри Миллер ещё 50 лет назад. Однако для доказательства его корректности требуется недавний результат OpenAI, связанный с квазигипотезой Римана (quasi-GRH)! Тест простоты AKS в своё время стал огромным достижением, удостоенным премий Гёделя и Фалкерсона в 2006 году. Но теперь он устарел. Безумные времена. 👉 @PythonPortal