Есть ли способ быстро проверить, простое ли число?

Answer 1

Есть множество тестов на простоту () В критерии Вормелла используется тот факт, что произведение нескольких чисел обращается в 0, если хотя бы один из сомножителей равен 0. Формула Вормелла выводится из критерия Вильсона: если x - простое число, то 1+ (x-1) ! делится на x без остатка. Есть простой вероятностный критерий, который следует из такого забавного факта - найдется такое число p, что выражение p в степени q (q=3) в степени n, округленное до левого целого возвращает простое число с номером n. При q = 3 таким значением будет 1. 4537508625483.