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

Задача. Дано натуральное число N, верно ли, что оно простое?

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

Как будем решать задачу

Введем с клавиатуры число N. Переменной k (количество делителей) присвоим 0.

Запустим цикл for с счетчиком i от 1 до N, будем проверять условие: если число делится на значение счетчика без остатка, то значение счетчика - это делитель числа, будем увеличивать количество k на 1.

За циклом проверим условие: если количество делителей равно 2, то число простое (сообщение 'верно'), иначе число не простое (сообщение 'неверно').

Программа решения на языке Паскаль (неэффективный алгоритм):

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.

Результат запуска программы

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