В 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: пока я писал ответ вопрос переформулировали и теперь таблицы простых чисел, компьютер и калькулятор применять по условию нельзя. Новый ответ: уважаемый автор вопроса, развивайте навыки вычисления в уме, либо навыки разложения полиномиальных выражений на бумажке (удачи вам с разложением разностей в степени, например, несколько миллиардов). Чудес не бывает, считать все равно придется.
Я всего лишь добавил условие, что нельзя пользоваться таблицей простых чисел)
В любом случае, большое спасибо за ответ.
Да, ответ достаточно полный. Однако могу кое-что добавить. Если число чётное, хоть большое, хоть маленькое (кроме 2) или заканчивается на 5 (кроме 5), простым оно быть не может. Остальные числа проверяйте указанной формулой.