Цикл "поки" та його використання, Детальна інформація

Приклад 7. Прості числа 2, 3, 5, 7, 11, 13, … розташовані в натуральному ряду дуже загадковим чином. Нехай треба обчислити просте число за його номером у цій послідовності. Є формула, що задає просте число за його номером k, але обчислення за нею не простіші, ніж "лобові":

Йти натуральним рядом і рахувати, скільки простих чисел зустрілося.

Коли цей рахунок доходить до k, ми одержуємо те, що нам треба.

Це і є алгоритм пошуку k-го простого числа. Уточнимо його.

Нехай k>0. Означимо для зберігання натуральних чисел, що перебираються, змінну m. З алгоритму випливає, що нам потрібна ще змінна для збереження кількості простих чисел, які вже зустрілися. Нехай cs – ім'я цього "лічильника простих чисел". Спочатку cs=1, m=2 (у значенні лічильника враховано перше просте число 2). Далі починається цикл:

якщо умова продовження cs
Ось переклад останніх фраз на Паскаль у вигляді програми з функцією issimple із попереднього прикладу:

program simpi(input, output);

var k, m, cs: integer;

function issimple(n:integer):boolean;

...

end; {issimple}

begin

writeln('задайте номер(>0):');

readln(k);

cs:=1; m:=2;

while cs
begin

m:=m+1;

if issimple(m) then cs:=cs+1

end;

{cs=k, значення m – шукане}

writeln( k, '-е просте : ', m)

end.

\xF0E7

Приклад 8. Як відомо, кожне натуральне число, більше 1, однозначно розкладається в добуток простих співмножників, наприклад, 13=13, 105=3\xF0D7 5\xF0D7 7, 72=2\xF0D7 2\xF0D7 2\xF0D7 3\xF0D7 3 тощо. Щоб побудувати розклад довільного числа, або його факторизацію, знайдемо його найменший дільник (очевидно, що він простій), запишемо його і поділимо на нього число. Подальші співмножники розкладу утворюються так само доти, поки в результаті ділень не утвориться 1. Наприклад, 36=2\xF0D7 18 (виписали 2), 18=2\xF0D7 9 (2), 9=3\xF0D7 3 (3), 3=3\xF0D7 1 (3).

Очевидно, що найменший дільник частки від ділення не може бути менше, ніж найменший дільник діленого. Тому після чергового ділення пошуки такого найменшого дільника можна починати не з 2, а з останнього дільника.

Алгоритм друкування розкладу n оформимо у вигляді процедури simpdivisors із параметром n ("divisor" означає "дільник"). Можливі дільники будуть значеннями змінної k.

Спочатку k=2. Потім, поки n>1, перевіряється подільність n на k. Якщо ділиться, то виписується значення k і виконується ділення, інакше k збільшується, тому що менших дільників уже бути не може.

Наведене описання обчислень уточнюється в такому вигляді: