сек.)
Які числа називаються простими? Які складовими?
Як визначити просте число?
Задача2. Скласти функцію, що визначає чи є натуральне число X простим? (1? X? 109)
Хлопці зазвичай пропонують скористатися Завданням 1, підрахувавши кількість дільників. Пропоную знайти шляхи удосконалення алгоритму. Помічаємо, що:
а) просте число не може бути парним (за винятком 2),
б) непарне число не може мати парних дільників,
в) якщо знайшли хоч один дільник, то число - складене і можна зупинити цикл.
Враховуючи зауваження, складаємо функцію:
Function Prost (x: longint): boolean; d: longint;
If x mod 2=0 then Prost:=(x=2)
else begin
d:=3;
while (int64 (d) * d lt;=x) and (x mod d lt; gt; 0) do:=d + 2;
Prost:=(int64 (d) * d gt; x) and (x lt; gt; 1);
end;
end;
Як знайти всі прості числа на заданому целочисленном проміжку?
Задача3. Знайти всі прості числа на проміжку від 2 до N (N? 106).
Хлопці зазвичай пропонують в циклі скористатися функцією Prost з Задачі2. З'ясовуємо складність такого алгоритму: N *. При N=106 отримаємо 1 млрд. Дій. Отже, треба шукати більш швидке рішення.
чув хто-небудь з вас про Решето Ератосфена?
Виписую на дошці в ряд всі числа від 1 до 27 і показую принцип Решета:
викреслюю 1, викреслюю всі числа кратні 2, кратні 3, кратні 5 (крім їх самих). Залишилися тільки прості числа на дошці. Складаємо програму:
p [1]:=false; i:=2 to N do p [i]:=true;
i:=2; int64 (i) * i lt;=N do beginp [i] then begin j:=int64 (i) * i;
while j lt;=N do begin
p [j]:=false; j:=j + i;
end;
end;
if i=2 then i:=3 else i:=i + 2 ;; i:=2 to N do if p [i] then write (i,);
У вищій математиці доведено, що складність алгоритму: N * log2 (log2N), значить при N=106 отримуємо 4500000. дій і встигнемо за 1 сек знайти відповіді.
.Закрепленіе нового матеріалу (репродуктивний метод навчання, індивідуальна форма роботи).
Самостійна робота в тестуючої системі. Учням пропонується завантажити систему програмування Free Pascal, зайти на сайт acmp, самостійно скласти і відіслати на перевірку в тестуючу систему програму для вирішення Завдання під № 349.
Завдання (№ 349). Знайти всі прості числа від M до N. (2 lt;=M lt;=N lt;=10 6)
Ділю учнів на два варіанти і пропоную вирішити завдання за допомогою функції Prost і за допомогою Решета Ератосфена.
. Підведення підсумків уроку. Рефлексія.
З'ясовую, скільки часу виконувалася програма завдання № 349 кожним із способів.
У скільки разів алгоритм Решета Ератосфена виявився швидшим, ніж використання функції Prost?
Які нові алгоритми сьогодні ви дізналися на уроці? Розкажіть основну ідею цих алгоритмів.
Домашнє завдання:
1) Повторити алгоритми: НСД, знаходження дільників, визначення просте чи число, алгоритм Решета Ератосфена;
) на сайті acmp здати № 60 (надпростий число), № 171 (Кількість дільників).
Учитель інформатики Лактин В.П.
Вітебськ, 2013р.
