Jak sprawdzić, czy liczba jest pierwsza? Dzielenie po kolei
Funkcja is_prime w najprostszej wersji
Dlaczego wystarczy dzielić do pierwiastka z liczby?
Moduł math, funkcja sqrt i wersja, która liczy krócej
Podręcznik: s. 124–127 oraz dodatki 8 i 9.
Rozgrzewka · 3 minuty
Funkcja, czyli nazwany kawałek programu
Wracamy do funkcji division_remainder z poprzedniej lekcji.
Od jakiego słowa zaczyna się definicja funkcji w Pythonie i jakim znakiem kończy się jej pierwszy wiersz?
Co robi w funkcji słowo return?
Piszemy def division_remainder(a, b):, a wywołujemy division_remainder(number, 3). Które nazwy są parametrami formalnymi, a które aktualnymi?
podręcznik s. 121–123 i dodatek 7, s. 226
Część 1 · Pomysł na test
Dzielimy po kolei, aż znajdziemy dzielnik
Liczba jest złożona, gdy ma jakikolwiek dzielnik różny od 1 i od niej samej. Wystarczy więc dzielić ją kolejno przez 2, przez 3 i tak dalej, aż do n − 1. Jeden trafiony dzielnik kończy sprawę: dalej nie ma czego szukać.
Podręcznik Informatyka na czasie 2, s. 124 (8.3 Test pierwszości liczby, opis najprostszego algorytmu i ramka „Specyfikacja”)
Część 1 · Kod
Funkcja is_prime
1. def is_prime(n):
2. for i in range(2, n):
3. if n % i == 0:
4. return False
5. return True
6.
7. number = int(input("Podaj liczbę: "))
8.
9. if is_prime(number):
10. print("Liczba pierwsza")
11. else:
12. print("Liczba złożona")
Linie 1.–5. to definicja funkcji. Sprawdza ona podzielność liczby przez wszystkie liczby od 2 do n − 1.
Linia 4. Gdy dzielnik się znajdzie, funkcja zwraca False (fałsz) i od razu kończy działanie, więc kolejnych dzieleń już nie wykonuje.
Linia 5. Gdy żaden dzielnik się nie znalazł, funkcja zwraca True (prawda).
Linia 9. Zapis if is_prime(number) czytamy jako „jeśli is_prime(number) to prawda”.
Podręcznik Informatyka na czasie 2, s. 124 (8.3 Test pierwszości liczby, kod źródłowy programu „Test pierwszości” i jego omówienie)
Część 1 · Krok po kroku
Ta sama funkcja na kartce
Żeby zrozumieć funkcję, przechodzimy ją ręcznie. Oto przykład dla liczby 15.
Krok
Wartość i
Obliczenie n % i
Co robi funkcja
1
2
15 % 2 = 1
reszta różna od zera, pętla bierze kolejne i
2
3
15 % 3 = 0
warunek prawdziwy, return False, funkcja kończy działanie
Dla liczby złożonej tabela urywa się na pierwszym dzielniku. Dla liczby pierwszej ciągnie się do i równego n − 1.
Ciekawostka. W latach 90. XX wieku producent procesorów musiał wymienić cały model, bo dzielił z dokładnością 9 zamiast 19 miejsc po przecinku. Wadę zauważył matematyk Thomas Nicely, gdy liczył stałą Bruna. Wymiana kosztowała firmę 475 milionów dolarów.
Podręcznik Informatyka na czasie 2, s. 124 (8.3 Test pierwszości liczby, ramka „Warto wiedzieć” o błędzie procesora) · ciekawostka: en.wikipedia.org/wiki/Pentium_FDIV_bug
Część 2 · Mniej dzieleń
Wystarczy dzielić do pierwiastka
Gdy liczbę złożoną rozpiszemy jako iloczyn dwóch czynników większych od 1, to jeden z nich zawsze jest mniejszy lub równy pierwiastkowi z tej liczby. Dzielnik właściwy to każdy dzielnik mniejszy od samej liczby.
Wniosek: najmniejszy dzielnik właściwy liczby złożonej n jest mniejszy bądź równy pierwiastkowi z n. Jeśli do pierwiastka nic nie podzieliło liczby, dalej też nic jej nie podzieli.
Podręcznik Informatyka na czasie 2, s. 125 (8.3 Test pierwszości liczby, ulepszony algorytm, przykłady rozkładów liczb 36, 100 i 42, ramka „Warto wiedzieć” o dzielniku właściwym)
Część 2 · Moduł math
Skąd wziąć pierwiastek w Pythonie?
Pierwiastkowanie nie jest w Pythonie zwykłym działaniem, takim jak dodawanie czy dzielenie. Gotowe funkcje matematyczne leżą w modułach.
Moduł to plik z rozszerzeniem .py, w którym ktoś zebrał definicje funkcji dotyczących jednego zagadnienia. To jak szuflada z narzędziami do jednej roboty. Pierwiastek daje funkcja sqrt z modułu math.
Żeby użyć funkcji sqrt, dopisujemy na początku programu:
from math import sqrt
Bez tego wiersza Python nie wie, co znaczy sqrt, i przerwie program. Wynik ma część ułamkową, dlatego bierzemy z niego część całkowitą przez int().
Podręcznik Informatyka na czasie 2, s. 125–126 (8.3 Test pierwszości liczby, pojęcia z marginesu: operacja pierwiastkowania, moduł, funkcja sqrt, moduł math) i s. 227 (dodatek 8 Operatory i funkcje matematyczne, wynik sqrt(2.0))
Część 2 · Kod
Ulepszony test pierwszości
1. from math import sqrt
2.
3. def is_prime(n):
4. if n == 2:
5. return True
6. if n % 2 == 0:
7. return False
8.
9. root = int(sqrt(n))
10. for i in range(3, root+1, 2):
11. if n % i == 0:
12. return False
13. return True
14.
15. number = int(input("Podaj liczbę: "))
16.
17. if is_prime(number):
18. print("Liczba pierwsza")
19. else:
20. print("Liczba złożona")
Linie 4.–7. Dwójka od razu jest pierwsza, każda inna parzysta jest złożona.
Linia 9. Zmienna root to część całkowita pierwiastka z n.
Linie 10.–13. Pętla bierze już tylko liczby nieparzyste: trzeci argument funkcji range to krok o długości 2.
Podręcznik Informatyka na czasie 2, s. 126 (8.3 Test pierwszości liczby, kod źródłowy programu „Ulepszony test pierwszości” i jego omówienie)
Część 3 · Zysk
O ile mniej pracy dla komputera?
Obie wersje dają ten sam wynik, ale różnią się liczbą wykonanych dzieleń. Oto porównanie dla liczby 53, która jest pierwsza, czyli dla przypadku najgorszego: pętla musi dojść do końca.
Dobra rada. Funkcja range(k, n) tworzy ciąg liczb od k do n − 1, a nie do n. Dlatego w kodzie stoi root+1: bez tej jedynki nieparzysty pierwiastek nigdy nie zostałby sprawdzony.
Podręcznik Informatyka na czasie 2, s. 126 (8.3 Test pierwszości liczby, omówienie ulepszeń i ramka „Dobra rada” o funkcji range)
Ćwiczenie · na kartce · 12 minut
Ćwiczenie: policz dzielenia
Podpisz kartkę. Narysuj tabelę z prawej i wypełnij ją dla najprostszej wersji is_prime dla n = 9, a niżej drugą dla n = 11.
Zrób to samo dla wersji ulepszonej, znowu dla n = 9 i n = 11.
Bez rysowania tabeli policz, ile dzieleń wykona każda wersja dla n = 97 i ile dzieleń oszczędza wersja z pierwiastkiem.
Krok | i | n % i | Co robi funkcja
1 | | |
2 | | |
3 | | |
Liczba dzieleń:
Wynik:
Dla chętnych (dom): plik primality_test.py z obiema wersjami funkcji, uruchomiony dla trzech własnych liczb trzycyfrowych.
Podręcznik Informatyka na czasie 2, s. 125 (ćwiczenie 3b) i s. 126 (ćwiczenie 5b), oraz s. 127 (Zadania 1.–6.)
Część 3 · Pytania kontrolne
Trzy pytania na koniec
Dlaczego funkcja is_prime kończy działanie już przy pierwszym znalezionym dzielniku?
Skąd wiadomo, że przy sprawdzaniu pierwszości wystarczy dzielić do pierwiastka z liczby?
Co trzeba dopisać na początku programu, żeby użyć funkcji sqrt, i co się stanie bez tego wiersza?
Podręcznik Informatyka na czasie 2, s. 124–126 (8.3 Test pierwszości liczby)
Część 3 · Podsumowanie
A jak to wygląda w produkcji?
Na lekcji
W produkcji
Status
Pierwiastek jako int(sqrt(n))
Python ma funkcję math.isqrt(n): zwraca całkowity pierwiastek bez przybliżenia, więc przy wielkich liczbach nie pomyli się o jeden.
zastępowane
Dzielenie po kolei przez wszystkie liczby
Liczby w szyfrowaniu mają setki cyfr, dzielenie próbne trwałoby za długo. Stosuje się test Millera-Rabina.
zastępowane
Liczba pierwsza jako zadanie z lekcji
Klucze szyfrujące powstają z dużych liczb pierwszych. Na tym stoi bezpieczeństwo połączenia z bankiem.
nadal w użyciu
Funkcja sqrt wzięta z modułu
Nikt nie pisze od zera pierwiastków, dat ani obsługi sieci: bierze się gotowe moduły.
nadal w użyciu
Słowa kluczowe wypisane w tabeli
Edytor podświetla je sam i nie pozwala nazwać tak zmiennej.
narzędzia
Ściąga: funkcje modułu math i słowa kluczowe
sqrt(2.0) -> 1.41421 pierwiastek kwadratowy (przyblizenie)
log10(2.0) -> 0.30103 logarytm dziesietny (przyblizenie)
ceil(2.5) -> 3 zaokraglenie w gore
floor(2.5) -> 2 zaokraglenie w dol
Słowa kluczowe poznane do tej pory:if, else, while, for, def, return, and, or, not, True, False, in, is, import, from. Tak nie wolno nazwać żadnej zmiennej ani funkcji: te nazwy są zarezerwowane dla samego języka.
W spisie pozostałych słów kluczowych podręcznik podaje field. Takiego słowa w Pythonie nie ma, chodzi o yield. Listę sprawdziłem w docs.python.org/3/reference/lexical_analysis.html. Nawet w podręczniku zdarzają się literówki.
math.isqrt i math.sqrt: docs.python.org/3/library/math.html · ściąga: podręcznik s. 227–228 (dodatki 8 i 9) · lista słów kluczowych: docs.python.org/3/reference/lexical_analysis.html · test Millera-Rabina: podręcznik s. 120 (8.1, ramka „A to ciekawe”)