Пояснення до алгоритму. Найменше просте число – це двійка

Найменше просте число – це двійка. Спочатку передбачається, що задане число – просте, тому р=0. Потім здійснюється низка перевірок, в результаті яких р може набути значення 1 (якщо це число 1) або 2 (якщо це число складене). Перевірку дільників числа достатньо робити до кореня квадратного з цього числа. Результат видається в комірці р у вигляді:

Потім аналізується вміст комірки р і залежно від її вмісту видається результат. Звичайно цей алгоритм записують у вигляді алгоритму-функції і використовують як допоміжний.

Алгоритм мовою Паскаль має вигляд:

Program Simple;

var n: longint; i: word;

Begin

write (‘ Введіть натуральне число >‘);

readln (n);

if n=1

then writeln (‘ Число дорівнює 1 ‘);

else if n=2

then writeln (‘Число_’, n ‘_просте’)

Else begin

i:=3;

while (i<=sqrt(n)) and (n mod i< >0)

do i:=i+2;

if n mod i=0

then writeln (‘Число_’, n, ‘_складене‘);

else writeln (‘Число_’, n, ‘_просте’);

end;

End.

У запропонованому варіанті враховано, що єдине парне просте число – це 2. Якщо введено саме це число, про це видається відповідне повідомлення. Решта простих чисел – непарні, а тому перевіряється подільність тільки на непарні числа (початкове значення і=3, а крок зміни 2). До того ж, умова у циклі while написана з урахуванням того, що всі непарні значення і перебираються, доки задане число n не поділиться на і та і не перевищить квадратного кореня з n.

Після виходу з циклу залишається з’ясувати, за якою умовою він припинив роботу. Якщо за першою (число поділилося націло) число складене, в протилежному випадку – просте.

Результати покрокового виконання алгоритму при n=25 подано в таблиці (розглядаємо розв’язування мовою НАМ).

Для закріплення попереднього матеріалу наводимо блок-схему алгоритму «Просте число»

(схема 9).

Поиск по сайту: