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:

def 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:

def 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.

def 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 pierwsza p, gdzie p > 2, jest liczbą niepodzielną przez żadną z liczb należących do przedziału od 2 do p-1.

Ta druga definicja daje nam wskazówkę, jak szukać liczb pierwszych. Dla danej liczby p  wystarczy sprawdzić, czy dzieli się bez reszty przez jakąś liczbę z przedziału od 2 do p-1. Jeśli tak, to p nie jest liczbą pierwszą. Jeśli żadna z liczb z przedziału od 2 do p-1 nie dzieli liczby p, p jest liczba pierwszą.

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.

def 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 p > 2 (dlaczego?).

Ćwiczenia

1. Napisz program, który odczyta z klawiatury liczbę i sprawdzi, czy jest liczbą pierwszą. Jeśli tak, program ma wypisać tekst 'LICZBA JEST PIERWSZA'. W przeciwnym razie ma wypisać tekst 'LICZBA NIE JEST PIERWSZA'.
2. Napisz program, który wyszukuje liczby pierwsze w zakresie odczytanym z klawiatury.
3. Napisz program, który znajdzie zadaną ilość liczb pierwszych począwszy od liczby 2.

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ą:

def 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 liczbą 2. Jeśli tak, to zwracamy True, ponieważ liczba 2 jest pierwsza. Jeśli nie jest to liczba 2, to sprawdzamy jej podzielność przez 2. Jeśli liczba p dzieli się przez 2 (a sama nie jest równa 2, co wyeliminowała poprzednia instrukcja if), to nie może być liczbą pierwszą. Kończymy zatem zwracając False.

Dalej tworzymy pętlę, przechodzącą przez wartości od 3 do p-1. W pętli sprawdzamy podzielność liczby p przez te wartości. Jeśli któraś z nich dzieli p, to p nie jest liczbą pierwszą, kończymy zatem i zwracamy wynik False. Gdy pętla się zakończy, to będzie to znaczyło, iż żadna z wartości nie dzieliła liczby p (dlaczego?). Zatem p musi być liczbą pierwszą. Funkcję kończymy z wynikiem True.

Wyszukiwanie liczb pierwszych podanym wcześniej sposobem jest bardzo nieefektywne dla dużych n. Początkowo program działa szybko, później wyraźnie zwalnia, aby na  końcu osiągnąć wręcz żółwie tempo pracy. Aby przekonać się, iż liczba p jest liczbą pierwszą, algorytm musi wykonać p-2 testy. Zastanówmy się nad tym, czy algorytm faktycznie powinien sprawdzać podzielność liczby p w całym przedziale <2, p-1>.

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 z p do p-1 może leżeć co najwyżej jeden czynnik. Gdyby było ich więcej, to ich iloczyn przekroczyłby wartość liczby p (dlaczego?). Skoro drugi czynnik nie może być większy od pierwiastka z p, to musi być od niego mniejszy lub równy. Z kolei przy teście na pierwszość liczby p wystarczy nam, iż znajdziemy pierwszą podzielność, aby wyeliminować p jako liczbę pierwszą Wynika z tego prosty wniosek – podzielność liczby p wystarczy sprawdzić dla dzielników z przedziału od 2 do pierwiastka całkowitego z  p. Jeśli żaden podzielnik z tego przedziału nie dzieli p, to p jest pierwsze, ponieważ w pozostałej części przedziału <2, p-1> nie mogą już wystąpić czynniki p (dlaczego?).

def 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.

Przykłady:

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ę.

Przykłady:

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.

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ę

44100 = 2×2×3×3×5×5×7×7

# 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.

# 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 append( ) pozwala dołączyć do tablicy nowy element dowolnego typu:

# Tablica/lista
#--------------

a = [1,5,7,2]
print(a)
a.append(3)
print(a)

Funkcja pop( ) ma działanie odwrotne, usuwa z tablicy ostatni element:

# 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.

# 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:

# 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 len( ) (podobnie jak dla liczby znaków w tekście). Poniższy program wyświetla kolejne elementy tablicy:

# 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 input( ). Skopiuj do schowka podany ciąg liczb, a następnie uruchom program i wklej ze schowka liczby:

61 12 73 44 9 15 13 2 7 5

# 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 split( ) rozbija tekst na poszczególne elementy. Znakiem rozdzielającym jest standardowo spacja. Wynikiem jest lista zbudowana z kolejnych elementów, np:

print("Miś Uszatek lubi miodek".split())

Poniższy program odczytuje z wejścia tablicę liczb i oblicza ich sumę:

# 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:

# 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)

Zadania

1. Napisz program, który odczyta ciąg liczb całkowitych, a następnie policzy ile z nich jest ujemnych, np:
   8 5 -4 3 -7 5 -11
   wynik 3
2. Napisz program, który odczyta ciąg liczb całkowitych, a następnie policzy ile z nich jest parzystych, np:
   8 5 4 3 7 5 12 2
   wynik 4
3. Napisz program, który odczyta ciąg liczb całkowitych, a następnie wypisze każdą z nich w kolejnych wierszach i policzy ich iloczyn, np:
   8 5 4 3
   8
   5
   4
   3
   wynik 480

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ść s[i] będzie z kolei informowała o tym, czy liczba i pozostała w zbiorze (s[i]= true) lub została usunięta (s[i] = false).

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 4 = 2². Następnie dla wielokrotności liczby 3  pierwszą do wyrzucenia jest 9 = 3², gdyż 6 zostało wyrzucone wcześniej jako wielokrotność 2. Dla 5 będzie to 25 = 5², gdyż 10 i 20 to wielokrotności 2, a 15 jest wielokrotnością 3, itd. Pozwoli to  wyeliminować zbędne obiegi pętli usuwającej wielokrotności.

# 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()

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