Язык Паскаль. Верно ли, что число простое

Проверка числа на простоту: решение на Pascal

Постановка задачи

Дано натуральное число N. Необходимо определить, является ли оно простым.

Простое число - это натуральное число, имеющее ровно 2 делителя (1 и само число). Например: 2, 3, 5, 7, 11, 13.

Алгоритм решения

Используем следующий подход:

1. Вводим число N с клавиатуры
2. Инициализируем счетчик делителей k = 0
3. В цикле от 1 до N проверяем делимость числа N на текущее значение счетчика
4. Если делитель найден, увеличиваем счетчик k
5. После цикла проверяем: если k = 2, число простое

Решение на Pascal с пояснениями

program CheckPrimeNumber;
var
  i, n, k: integer;
begin
  // Ввод числа для проверки
  write('Введите натуральное число n=');
  readln(n);
  
  // Инициализация счетчика делителей
  k := 0;
  
  // Цикл поиска делителей
  for i := 1 to n do
    if n mod i = 0 then 
      k := k + 1;
  
  // Проверка количества делителей
  if k = 2 then
    writeln('верно')  // Число простое
  else
    writeln('неверно');  // Число составное
end.

Как работает программа:

• Программа запрашивает число для проверки
• Перебирает все возможные делители от 1 до N
• Подсчитывает количество делителей
• Выводит "верно", если делителей ровно 2 (число простое)
• Выводит "неверно" в противном случае

Примеры работы программы

Пример 1: Проверка простого числа

Введите натуральное число n=7
верно

Пример 2: Проверка составного числа

Введите натуральное число n=8
неверно

Оптимизация алгоритма

Данный алгоритм является неэффективным по следующим причинам:

• Проверяет все числа от 1 до N, хотя достаточно проверить до √N
• Продолжает проверку после нахождения более двух делителей

Попробуйте оптимизировать алгоритм, используя эти наблюдения.