Доказать простоту числа (что нет ни одного делителя кроме 1 и самого числа) сложно, потому что быстрого алгоритма для разложения числа на множители не существует.

Алгоритмы

Безопасное простое число

Псевдопростое число