Ответ:

Число является простым, если оно больше 1 и не имеет делителей, кроме 1 и самого себя. Для проверки достаточно рассмотреть делители от 2 до √n.

  1. Ввести целое число n.
  2. Если n < 2, вывести «Число не является простым» и завершить алгоритм.
  3. Положить d = 2.
  4. Пока d · d ≤ n: если n делится на d без остатка, вывести «Число не является простым» и завершить алгоритм; иначе увеличить d на 1.
  5. Если проверка завершилась и делитель не найден, вывести «Число является простым».

Граница d · d ≤ n равносильна проверке делителей до квадратного корня числа; если делитель больше √n, ему соответствовал бы меньший делитель, который уже был бы проверен.