simp:= true; tsn:= trunc(sqrt(n))+1; k:= 2;

while (k<tsn) and simp do

begin

if n mod k=0 then simp:=false;

k:=k+1

end;

issimple:=simp

Оформлення функції з заголовком

function issimple(n:integer):boolean

лишаємо для вправи. Відзначимо ще раз, що тіло функції треба записувати так, що при виконанні її виклику виконувався хоча б один оператор присвоювання з її ім'ям у лівій частині.?

З цього прикладу напрошується простий висновок: після того, як алгоритм розв'язання задачі написаний, майже ніколи не пізно і не завадить подумати про те, як його поліпшити.

Поліпшення алгоритму й програми можуть стосуватися таких цілком різних властивостей, як зрозумілість, обсяг пам'яті комп'ютера, що використовується, та кількість дій, заданих програмою. А ця кількість визначає тривалість виконання програми, яка іноді буває дуже істотною.

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

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

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

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

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

якщо умова продовження cs<k істинна, то треба перейти до ще неперевіреного значення m, перевірити, чи є воно простим, і якщо так, то збільшити значення лічильника cs. Коли значення cs досягає значення k, останнє перевірене число і є шуканим.

Ось переклад останніх фраз на Паскаль у вигляді програми з функцією 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<k do

begin

m:=m+1;

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

end;

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

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

end.

?

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

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

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

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

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

procedure simpdivisors(n:integer);

var k:integer;

begin

k:=2;

while n>1 do

begin

if n mod k = 0 then

begin writeln(k); n:=n div k end

else k:=k+1

end

end

?

Задачі

9. При яких значеннях n, простих чи складених, останні два поліпшення алгоритму в прикладі 4.6 є істотними?

10. Напишіть два варіанти програми з прикладу 4.7, означивши функцію issimple згідно першого й останнього варіантів алгоритму з прикладу 4.6. Порівняйте час виконання програм за тих самих достатньо великих значень n.

11. Програма simpi із прикладу 4.7 задає перебір усіх натуральних підряд. Його легко скоротити приблизно втричі, якщо не перевіряти числа, явно кратні 2 або 3. Справді, за будь-якого натурального m із шести чисел 6m, 6m+1, 6m+2, 6m+3, 6m+4, 6m+5 достатньо перевірити тільки друге й останнє, а інші чотири кратні 2 або 3 і не можуть бути простими. Написати програму, що задає такий скорочений перебір.

Недоліком програми simpi є також те, що k-е просте число може виявитися більшим, ніж maxint. Доповнити умову продовження її циклу так, щоб при m=maxint подальші збільшення m були неможливі.

12.* Написати програму друкування всіх "близнюків", тобто пар простих чисел вигляду 6m-1 і 6m+1 для m>0, наприклад, 5 і 7, 11 і 13, 17 і 19 (але не 23 і 25). Природно, поки що мова йде про числа, не більші від maxint (у розд. 12 ми опишемо, як подавати та обробляти "великі" числа).

13. Поміняти процедуру simpdivisors із прикладу 4.8 так, щоб дільники друкувалися не стільки разів, скільки вони входять у розклад, а по одному разу, але з указанням після знака "**" їх степеня, якщо він більше 1. Наприклад, 13**2 за n=169, 2**3*3**2 за n=144, 2*5**2 за n=50.