Сторінка
3
3. Числа прості й не тільки Приклад 6. Напишемо функцію визначення, чи є натуральне значення її параметра, більше 1, простим числом. Як відомо, число n є простим, якщо його додатними дільниками є лише 1 і n. Число 2 просте, а n>2 просте, якщо не ділиться без остачі на жодне з чисел 2, 3, … , n-1. Якщо ж воно ділиться хоча б на одне з них, то є не простим, а складеним. Отже, n – просте тоді й тільки тоді, коли (n=2) або (n>2 і n не ділиться на жодне з чисел 2, 3, … , n-1). Очевидно також, що n – складене, якщо n>2 і ділиться хоча б на одне з чисел 2, 3, … , n-1. Таким чином, при n>2 треба перевірити подільність n на кожне з чисел k=2, 3, … , n-1. Результат перевірок можна запам'ятати у вигляді кількості d дільників серед цих чисел. До початку перевірок d=0, тобто жодний дільник ще не знайдений, і з кожним знайденим дільником d збільшується на 1. Тоді умова d=0 є ознакою того, що число просте. Оформимо сказане у вигляді алгоритму: if n>2 then begin d:=0; для всіх k=2, 3, … , n-1 перевірити, чи ділиться n на k:
якщо ділиться, то d:=d+1 if d>0 then n – складене else n – просте end else n – просте Уточнимо цей алгоритм. Нехай issimple, тобто "є_простим" – ім'я функції, яку ми пишемо. Природно означити тип значень, що повертаються з неї, як булів. Тоді "n – просте" і "n – складене" уточнюються як issimple:=true і issimple:=false. На початку обчислень вважаємо, що число просте, тому присвоюємо issimple:=true. Тоді достатньо оператора розгалуження з умовою n>2 без else-гілки. Так само достатньо і скороченого оператора розгалуження з умовою d>0. Фраза "для всіх k=2, 3, … , n-1 перевірити, чи ділиться n на k" задає повторення тих самих дій: перевірка подільності n на k та підготування до наступної перевірки, тобто збільшення k на 1. Спочатку k=2. Умовою продовження перевірок, очевидно, є умова k<n. issimple:=true;
if n>2 then begin d:=0; k:=2; while k<n do begin if n mod k = 0 then d:=d+1; k:=k+1 end; if d>0 then issimple:=false end Цей алгоритм можна істотно поліпшити. Почнемо з дрібниць. За оператором "if d>0 then …" змінній issimple фактично присвоюється значення виразу not (d>0). Простіше написати: issimple:=not(d>0). Насправді змінна d взагалі не потрібна. Дійсно, значенням issimple буде false, якщо хоча б один раз виконується оператор d:=d+1. Замість нього напишемо issimple:=false. Крім того, якщо n=2, то умова продовження k<n хибна при початковому значенні k, тому перевірку умови n>2 можна взагалі вилучити:
issimple:= true; k:= 2;
while k<n do {при n=2 тіло циклу не виконується жодного разу й значенням issimple залишається true}
begin
if n mod k=0 then issimple:=false;
k:=k+1
end Друге. Після того, як у циклі змінна issimple одержала значення false, подальші перевірки не потрібні, тому що вже ясно, що n не просте. Тому до умови продовження слід додати, що issimple має значення "істина". А перевірка цієї умови задається таким виразом: issimple. Було б природно записати вираз (k<tsn) and issimple як умову продовження. Проте використання імені функції у виразі означає її виклик. Виклик функції тут зовсім ні до чого, тому цей вираз помилковий. Замість issimple скористаємося допоміжною змінною з ім'ям, наприклад, simp, додавши наприкінці issimple:=simp: 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):');
Завантажити реферат