Дано некоторое большое натуральное число. Каков самый быстрый способ узнать, простое ли оно, без компьютера, таблицы простых чисел и калькулятора?

Ответить
Ответить
Комментировать
3
Подписаться
1
2 ответа
Поделиться
АВТОР ВОПРОСА ОДОБРИЛ ЭТОТ ОТВЕТ

В 2002 году был опубликован новый метод определения простоты, это т.н. быстрый метод, названный тест AKS. Он является обобщением малой теоремы Ферма. Статья в википедии не очень читаемая, поэтому попробую описать его простыми словами.

Для натурального числа p берем выражение вида (x-1)^p-(x^p-1). Если выражение делится на p, то p - простое число. К примеру для p=3 имеем выражение

(x-1)^3-(x^3-1)=x^3-3x^2+3x-1-x^3+1

Единица, минус единица, икс в кубе и минус икс в кубе сокращаются, остается -3x^2+3x, это выражение очевидно делится на исходное p=3, следовательно 3 - простое число.

С небольшой модификацией эти полиномиальные вычисления можно ускорить:

Выражение вида (x-а)^p-(x^p-а) при поставлении нескольких разных а, позволяет достоверно определить простое число или нет и обрабатывается компьютером несколько быстрее чем изначальное и значительно быстрее чем более старые методы (кроме вероятностных).

Самый интересный с моей точки зрения вывод из всего этого состоит в том, что математика не стоит на месте, новые идеи, методы, новая математика появляются постоянно.

EDIT: пока я писал ответ вопрос переформулировали и теперь таблицы простых чисел, компьютер и калькулятор применять по условию нельзя. Новый ответ: уважаемый автор вопроса, развивайте навыки вычисления в уме, либо навыки разложения полиномиальных выражений на бумажке (удачи вам с разложением разностей в степени, например, несколько миллиардов). Чудес не бывает, считать все равно придется.

12

Я всего лишь добавил условие, что нельзя пользоваться таблицей простых чисел)

В любом случае, большое спасибо за ответ.

+1
Ответить
Прокомментировать

Да, ответ достаточно полный. Однако могу кое-что добавить. Если число чётное, хоть большое, хоть маленькое (кроме 2) или заканчивается на 5 (кроме 5), простым оно быть не может. Остальные числа проверяйте указанной формулой.

0
Прокомментировать
Ответить