Serwis Edukacyjny w I-LO w Tarnowie ![]() Materiały dla uczniów liceum |
Wyjście Spis treści Wstecz Dalej
Autor artykułu: mgr Jerzy Wałaszek |
©2025 mgr Jerzy Wałaszek |
SPIS TREŚCI |
Liczba 1 nie jest pierwszą, ponieważ dzieli się tylko przez 1, a nie posiada drugiego podzielnika różnego od 1. Przykłady liczb pierwszych:
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97 ...
Liczby pierwsze mają ogromne znaczenie we współczesnej informatyce. Na nich opierają się zaawansowane systemy szyfrujące używane przez banki, służby państwowe i wojsko. Dlatego umiejętność sprawdzania pierwszości liczby oraz generacji liczb pierwszych jest podstawową umiejętnością każdego adepta informatyki.
W języku Python funkcja jest blokiem kodu, który zostaje wykonany dopiero po wywołaniu. Funkcje definiujemy następująco:
def nazwa_funkcji(): blok kodu
Po zdefiniowaniu funkcję wywołujemy poprzez jej nazwę. Oto przykład:
Pythondef powitanie(): print("Witaj") print("w Pythonie") print("**********") print() for i in range(10): powitanie() |
Do funkcji możemy przekazywać parametry:
def nazwa_funkcji(parametry): blok kodu
Parametry mają postać podobną do zmiennych. Funkcja ma do nich dostęp poprzez ich nazwy:
Pythondef dodaj(a, b): suma = a + b print(a,'+',b,'=',suma) for i in range(10): dodaj(5, 2 * i) |
Funkcja może zwracać wynik za pomocą instrukcji return:
def nazwa_funkcji(parametry): obliczenia return wynik
Jeśli komputer napotka w kodzie funkcji instrukcję return, to zwróci wartość i zakończy wykonywanie funkcji.
Pythondef pierwiastek(a): p = a ** 0.5 return p for i in range(2,26): print("pierwiastek z",i, "=",pierwiastek(i)) |
Podana na początku rozdziału definicja liczby pierwszej jest dla nas niewygodna. Zapiszmy ją zatem w postacie równoważnej:
Liczba
Ta druga definicja daje nam wskazówkę, jak szukać liczb
pierwszych. Dla danej
Napiszmy funkcję, która sprawdzi, czy liczba przekazana jej w argumencie jest pierwsza i zwróci wartość logiczną True, jeśli tak; w przeciwnym razie zwróci wartość logiczną False.
Pythondef is_prime(p): for i in range(2,p): if p % i == 0: return False return True |
Zwróć uwagę, iż w kodze funkcji znajdują się dwie instrukcje return.
Nie jest to sprzeczność, ponieważ pierwsza z nich będzie wykonywana, jeśli
warunek instrukcji if w pętli for zostanie spełniony
(liczba p NIE
JEST PIERWSZA, bo dzieli się przez i), a druga zostanie wykonana po zakończeniu
pętli for (liczba p nie dzieli się przez żadną z liczb
i, zatem JEST
PIERWSZA). Funkcja działa poprawnie dla liczb
Za wyjątkiem liczby 2, wszystkie pozostałe liczby pierwsze są niepodzielne przez 2. Jeśli uwzględnimy ten fakt, to zmniejszymy ilość dzieleń przez połowę. Zmodyfikujmy zatem naszą funkcję wyszukującą:
Pythondef is_prime(p): if p == 2: return True if not p % 2: return False for i in range(3,p,2): if p % i == 0: return False return True |
Na początku sprawdzamy, czy p jest
Dalej tworzymy pętlę, przechodzącą przez wartości
Wyszukiwanie liczb pierwszych podanym wcześniej sposobem jest bardzo nieefektywne dla
Jeśli liczba p jest złożona, to rozkłada się na iloczyn czynników pierwszych (czyli takich, które są liczbami pierwszymi):
p = d1 × d2 × … × dk
Czynników tych musi być przynajmniej 2 i muszą one być różne od 1 i p
(dlaczego?). Prosta analiza pokazuje nam, iż w przedziale od pierwiastka
Pythondef is_prime(p): if p == 2: return True if not p % 2: return False g = int(p ** 0.5) for i in range(3,g+1,2): if p % i == 0: return False return True |
Każda liczba naturalna większa od 1 jest albo liczbą pierwszą (która dzieli się tylko przez 1 i siebie samą), albo liczbą złożoną (która posiada dodatkowe dzielniki). Czynnikiem pierwszym danej liczby jest każda liczba pierwsza, która dzieli daną liczbę. Podstawowe twierdzenie arytmetyki mówi, iż każda liczba naturalna większa od 1 da się przedstawić w postaci iloczynu liczb pierwszych, które są jej dzielnikami.
2 = 2 (liczba pierwsza) 3 = 3 (liczba pierwsza) 4 = 2 × 2 (liczba złożona) 5 = 5 (liczba pierwsza) 6 = 2 × 3 (liczba złożona) 7 = 7 (liczba pierwsza) 8 = 2 × 2 × 2 (liczba złożona) 9 = 3 × 3 (liczba złożona) ...
Rozkład danej liczby (naturalna i większa od 1) na czynniki pierwsze polega na znalezieniu wszystkich liczb pierwszych, których iloczyn daje daną liczbę.
28 = 2 × 2 × 7 66 = 2 × 3 × 11 45477488 = 2 × 2 × 2 × 2 × 7 × 7 × 19 × 43 × 71
Rozkład taki jest jednoznaczny, co oznacza, iż daną liczbę da się przedstawić tylko przy pomocy dokładnie jednego iloczynu liczb pierwszych. Najprostszym sposobem znalezienia takiego rozkładu jest metoda próbnych dzieleń.
Będziemy sprawdzać podzielność liczby p przez kolejne liczby naturalne od 2 do pierwiastka całkowitego z p. Jeśli liczba p będzie podzielna przez daną liczbę, to liczbę wyprowadzimy na wyjście, a za nowe p przyjmiemy wynik dzielenia i próbę dzielenia będziemy powtarzać dotąd, aż nie będzie to już możliwe. Wtedy przejdziemy do następnego dzielnika. Gdy przekroczymy wartość pierwiastka, to liczba zredukuje się albo do 1, albo do ostatniego czynnika większego od pierwiastka.
Przykład:
Rozłożyć liczbę 44100 na czynniki pierwsze.
Podział | Reszta | Czynnik | Znalezione czynniki | Uwagi |
44100:2 = 22050 |
0 |
2 |
2 |
dzieli się |
22050:2 = 11025 |
0 |
2 |
2 2 |
dzieli się |
11025:2 = 5512 |
1 |
X |
2 2 |
nie dzieli się |
11025:3 = 3675 |
0 |
3 |
2 2 3 |
dzieli się |
3675:3 = 1225 |
0 |
3 |
2 2 3 3 |
dzieli się |
1225:3 = 408 |
1 |
X |
2 2 3 3 |
nie dzieli się |
1225:4 = 306 |
1 |
X |
2 2 3 3 |
nie dzieli się |
1225:5 = 245 |
0 |
5 |
2 2 3 3 5 |
dzieli się |
245:5 = 49 |
0 |
5 |
2 2 3 3 5 5 |
dzieli się |
49:5 = 9 |
4 |
X |
2 2 3 3 5 5 |
nie dzieli się |
49:6 = 8 |
1 |
X |
2 2 3 3 5 5 |
nie dzieli się |
49:7 = 7 |
0 |
7 |
2 2 3 3 5 5 7 |
dzieli się |
7:7 = 1 |
0 |
7 |
2 2 3 3 5 5 7 7 |
dzieli się |
Kończymy, ponieważ wynik ostatniego dzielenia jest równy 1 |
44100 = 2×2×3×3×5×5×7×7
Python# Rozkład liczby naturalnej # na czynniki pierwsze #-------------------------- # Odczytujemy liczbę n = int(input("Wpisz liczbę: ")) # Obliczamy granicę # wyszukiwania podzielników, czyli # pierwiastek całkowity z n g = int(n ** 0.5) # Szukamy czynników pierwszych print(n, ": ", end="") for i in range(2, g + 1): # Dopóki dzielnik i dzieli # liczbę n, wyprowadzamy go # na wyjście i dzielimy przez # niego liczbę n, co usuwa # z niej jeden czynnik while n % i == 0: print(i, end=" ") n //= i # Pętlę kończymy, gdy liczba # n zredukowała się do 1, # czyli zostały już znalezione # wszystkie czynniki. if n == 1: break # Ostatni czynnik większy od # pierwiastka g? if n > 1: print(n) else: print() |
Tablica (ang. array) lub wektor (ang. vector) jest złożoną strukturą danych (ang. compound data structure) zbudowaną z ciągu elementów tego samego typu. W pamięci komputera elementy tablicy są ułożone kolejno jeden obok drugiego. Dostęp do elementu odbywa się poprzez numer zwany indeksem. Na podstawie indeksu, rozmiaru elementu oraz adresu początku tablicy komputer oblicza adres elementu i w ten sposób uzyskujemy do niego dostęp.
W języku Python tablica zwana jest również listą, ponieważ może zawierać różne elementy.
Poniższy program tworzy prostą tablicę o nazwie a i umieszcza w niej 4 liczby całkowite 1, 5, 7, 2. Na koniec wyświetla zawartość tablicy.
Python# Tablica/lista #-------------- a = [1,5,7,2] print(a) |
W języku Python tablica jest obiektem, który posiada własne
funkcje składowe (podobnie jak tekst).
Funkcja
Python# Tablica/lista #-------------- a = [1,5,7,2] print(a) a.append(3) print(a) |
Funkcja
Python# Tablica/lista #-------------- a = [1,5,7,2] print(a) a.append(3) print(a) a.pop() |
Dostęp do poszczególnych elementów tablicy jest wykonywany przy pomocy indeksów w klamrach kwadratowych. Każdy element posiada numer. Numery rozpoczynają się od zera.
Python# Tablica/lista #-------------- a = [1,5,7,2] print(a) a.append(3) print(a) a.pop() print(a) print(a[0],a[2]) |
Elementy tablicy zmieniamy przy pomocy operacji przypisania:
Python# Tablica/lista #-------------- a = [1,5,7,2] print(a) a[0] = 3 print(a) a[1] = 4 print(a) |
Tablicę możemy przetwarzać w pętli. Liczę elementów tablicy
zwraca funkcja
Python# Tablica/lista #-------------- a = [3,5,7,2,8,9] print(a) for i in range(len(a)): print("Element",i,":",a[i]) |
Tablicę możemy odczytać z wejścia przy pomocy funkcji
61 12 73 44 9 15 13 2 7 5
Python# Tablica/lista #-------------- # Odczytujemy liczby jako tekst t = input() print(t) # Tekst rozbijamy na kolejne teksty t = t.split() print(t) # Teksty zmieniamy w liczby for i in range(len(t)): t[i] = int(t[i]) print(t) |
Funkcja składowa
Pythonprint("Miś Uszatek lubi miodek".split()) |
Poniższy program odczytuje z wejścia tablicę liczb i oblicza ich sumę:
Python# Suma liczb w tablicy #--------------------- t = input().split() suma = 0 for i in range(len(t)): t[i] = int(t[i]) suma += t[i] print("suma",t,"=",suma) |
Kolejny program wyszukuje największą liczbę w odczytanym ciągu liczb:
Python# Największa z liczb w tablicy #----------------------------- t = input().split() for i in range(len(t)): t[i] = int(t[i]) if i == 0: maxt = t[0] elif t[i] > maxt: maxt = t[i] print("MAX",t,"=",maxt) |
Liczby pierwsze można wyszukiwać poprzez eliminację ze zbioru liczbowego wszystkich wielokrotności wcześniejszych liczb.
Przykład:
Mamy następujący zbiór liczb naturalnych:
{2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50}
Ze zbioru wyrzucamy wszystkie wielokrotności pierwszej liczby 2. Otrzymujemy następujący zbiór:
{2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50}
W zbiorze pozostały liczby nieparzyste – z wyjątkiem pierwszej liczby 2. Liczby podzielne przez dwa zostały wyeliminowane. Teraz eliminujemy wielokrotności kolejnej liczby 3. Otrzymamy następujący zbiór:
{2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50}
Teraz w zbiorze pozostały liczby niepodzielne przez 2 i 3 – z wyjątkiem pierwszych liczb 2 i 3. Zwróć uwagę, iż kolejna liczba 4 została już ze zbioru wyeliminowana. Skoro tak, to ze zbioru zniknęły również wszystkie wielokrotności liczby 4, ponieważ są one również wielokrotnościami liczby 2, a te wyeliminowaliśmy przecież na samym początku. Przechodzimy zatem do liczby 5 i eliminujemy jej wielokrotności otrzymując zbiór wynikowy:
{2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50}
Oprócz 2, 3 i 5 pozostałe w zbiorze liczby nie dzielą się już przez 2, 3 i 5. Liczba 6 jest wyeliminowana (wielokrotność 2), zatem przechodzimy do 7. Po wyeliminowaniu wielokrotności liczby 7 zbiór przyjmuje postać:
{2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50}
W zbiorze pozostały same liczby pierwsze.
{2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50}
Przy eliminacji wystarczy usunąć ze zbioru wielokrotności liczb leżących w przedziale od 2 do pierwiastka z n. Wyjaśnienie tego faktu jest identyczne jak w algorytmie szukania liczb pierwszych przez testowanie podzielności. Jeśli liczba p jest złożona, to musi posiadać czynniki pierwsze w przedziale od 2 do pierwiastka z p.
Powyższe operacje wyrzucania wielokrotności prowadzą do przesiania zbioru wejściowego. W zbiorze pozostają tylko liczby pierwsze, liczby będące wielokrotnościami poprzedzających je liczb zostają ze zbioru odsiane. Algorytm dokonujący tej eliminacji nosi nazwę sita Eratostenesa (ang. Eratosthenes' sieve) i jest jednym z najszybszych sposobów generowania liczb pierwszych.
Sito Eratostenesa jest algorytmem dwuprzebiegowym. Najpierw dokonuje on
eliminacji ze zbioru liczb złożonych oznaczając je w określony sposób, a w
drugim obiegu przegląda zbiór ponownie, wyprowadzając na wyjście liczby, które
nie zostały oznaczone. Podstawowe znaczenie w tym algorytmie ma wybór
odpowiedniej struktury danych do reprezentacji zbioru liczb. Na tym polu
można dokonywać różnych optymalizacji. W pierwszym podejściu zastosujemy tablicę
wartości logicznych s. Element
s[i] będzie odpowiadał liczbie
o wartości i.
Zawartość
Najpierw przygotowujemy tablicę reprezentującą zbiór liczbowy wypełniając ją wartościami logicznymi true. Odpowiada to umieszczeniu w zbiorze wszystkich liczb wchodzących w zakres od 2 do n. Następnie z tablicy będziemy usuwali kolejne wielokrotności początkowych liczb od 2 do pierwiastka całkowitego z n wpisując do odpowiednich elementów wartość logiczną false. Na koniec przeglądniemy zbiór i wypiszemy indeksy elementów zawierających wartość logiczną true – odpowiadają one liczbom, które w zbiorze pozostały.
Za pierwszą wielokrotność do wyrzucenia ze zbioru przyjmiemy kwadrat liczby
i. Przyjrzyj się naszemu przykładowi. Gdy wyrzucamy wielokrotności
liczby 2, to
pierwszą z nich jest
Python# Sito Eratostenesa #------------------ n = int(input()) s = [] for i in range(n+1): s.append(True) g = int(n ** 0.5) for i in range(2, g+1): if s[i]: w = i*i while w <= n: s[w] = False w += i for i in range(2, n+1): if s[i]: print(i, end=" ") print() |
Wynik: |
100 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 |
![]() |
Zespół Przedmiotowy Chemii-Fizyki-Informatyki w I Liceum Ogólnokształcącym im. Kazimierza Brodzińskiego w Tarnowie ul. Piłsudskiego 4 ©2025 mgr Jerzy Wałaszek |
Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone pod warunkiem podania źródła oraz niepobierania za to pieniędzy.
Pytania proszę przesyłać na adres email:
Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.
Informacje dodatkowe.