Простое число – натуральное число имеющее ровно два различных натуральных делителя – единицу и самого себя.

Я знаю несколько способов проверить число n на простоту:

  • посчитать все остатки от деления n на числа от 2 до
  • решето Эратосфена
  • вероятностный тест Ферма