V tomto návodu se dozvíte, jak vytvořit program v jazyce Python, který ověří, zda je dané číslo prvočíslo.
Pokud jste se někdy účastnili programátorských testů, jistě jste narazili na úlohu, která se týkala zjišťování, zda je zadané číslo prvočíslo. Nyní se naučíte, jak efektivně tento problém vyřešit.
V tomto tutoriálu:
- Zopakujeme si základní definici prvočísel,
- Napíšeme kód v Pythonu, který určí, zda je číslo prvočíslo, a
- Optimalizujeme tento kód pro dosažení algoritmu s časovou složitostí O(√n).
Pojďme se do toho pustit!
Co je to prvočíslo?
Začněme tím, že si zopakujeme základní vlastnosti prvočísel.
V teorii čísel se přirozené číslo n nazývá prvočíslem, pokud má přesně dva dělitele: číslo 1 a samotné číslo (n). Připomeňme si, že číslo i je dělitelem čísla n, pokud je n beze zbytku dělitelné číslem i. ✅
Následující tabulka uvádí několik čísel, jejich dělitele a informaci o tom, zda jsou prvočísla.
| n | Dělitelé | Je prvočíslo? |
| 1 | 1 | Ne |
| 2 | 1, 2 | Ano |
| 3 | 1, 3 | Ano |
| 4 | 1, 2, 4 | Ne |
| 7 | 1, 7 | Ano |
| 15 | 1, 3, 5, 15 | Ne |
Z této tabulky můžeme vyvodit následující:
- 2 je nejmenší prvočíslo.
- 1 je dělitelem každého čísla.
- Každé číslo n je dělitelem samo sebe.
Čísla 1 a n jsou tedy takzvaní triviální dělitelé libovolného čísla n. A prvočíslo nesmí mít žádné jiné dělitele než tyto dva.
To znamená, že při prohledávání čísel v rozsahu od 2 do n-1 nesmíme najít žádného dělitele, který by dělil n beze zbytku.
Algoritmus s časovou složitostí O(n) pro zjištění, zda je číslo prvočíslo v Pythonu
Nyní formalizujme výše uvedený postup do podoby funkce v Pythonu.
K procházení všech čísel od 2 do n-1 můžeme použít funkci `range()` v Pythonu.
Funkce `range(start, stop, step)` v Pythonu vrací objekt `range`. Můžeme tento objekt iterovat a získávat posloupnost čísel od `start` do `stop – 1` v daných krocích.
Protože potřebujeme množinu celých čísel od 2 do n-1, můžeme použít `range(2, n)` v kombinaci s cyklem `for`.
Postup bude následující:
- Pokud najdeme číslo, které dělí n beze zbytku, můžeme okamžitě konstatovat, že číslo není prvočíslo.
- Pokud projdeme celý rozsah čísel od 2 do n-1 a nenajdeme žádného dělitele čísla n, pak je číslo prvočíslo.
Funkce v Pythonu pro zjištění prvočísla
S použitím výše uvedeného můžeme definovat funkci `is_prime()` následovně:
def is_prime(n):
for i in range(2,n):
if (n%i) == 0:
return False
return True
Nyní si analyzujme definici funkce:
- Funkce `is_prime()` přijímá jako argument kladné celé číslo n.
- Pokud v určeném rozsahu (2, n-1) najdeme dělitele, funkce vrátí `False`, protože číslo není prvočíslo.
- Vrátí `True`, pokud projdeme celým cyklem bez nalezení dělitele.
Nyní funkci otestujeme s různými argumenty a ověříme správnost výstupu.
is_prime(2)
# True
is_prime(8)
# False
is_prime(9)
# False
is_prime(11)
# True
Výstup ukazuje, že 2 a 11 jsou prvočísla (funkce vrací `True`) a 8 a 9 prvočísla nejsou (funkce vrací `False`).
Jak optimalizovat funkci `is_prime()` v Pythonu
Zde můžeme provést malou optimalizaci. Podívejme se na dělitele čísel v tabulce níže:
| Číslo | Dělitelé |
| 6 | 1, 2, 3, 6 |
| 10 | 1, 2, 5, 10 |
| 18 | 1, 2, 3, 6, 9, 18 |
Vidíme, že jediný dělitel čísla n, který je větší než n/2, je samotné n.
To znamená, že nemusíme procházet rozsah až do n-1, ale můžeme cyklus provést pouze do n/2.
Pokud do n/2 nenajdeme netriviálního dělitele, nenajdeme ho ani za n/2.
Nyní upravíme funkci `is_prime()` tak, aby kontrolovala dělitele v rozsahu (2, n/2):
def is_prime(n):
for i in range(2,int(n/2)):
if (n%i) == 0:
return False
return True
Ověřme si výstup s několika voláními funkcí.
is_prime(9)
# False
is_prime(11)
# True
I když se zdá, že jsme provedli optimalizaci, z hlediska časové složitosti není tento algoritmus efektivnější než ten předchozí. Oba mají časovou složitost O(n), tedy lineární vzhledem k n.
Můžeme to udělat lépe? Ano, můžeme!
▶️ Pokračujte další částí a zjistěte, jak zlepšit časovou složitost testování prvočísel.
Algoritmus s časovou složitostí O(√n) pro testování prvočísel v Pythonu
Ukazuje se, že dělitelé čísla se vyskytují v párech.
Pokud je a dělitelem čísla n, pak existuje také dělitel b takový, že axb = n, nebo jednoduše ab = n.
Ověřme si to na příkladu.
Níže uvedená tabulka ukazuje dělitele čísla 18 uspořádané do párů. Pokud chcete, můžete si to ověřit na dalších číslech.
Všimněte si, že √18 je přibližně 4,24.
Ve dvojicích dělitelů (a, b) vidíme, že pokud je a menší než 4,24, pak b je větší než 4,24 – v tomto případě (2, 18) a (3, 6).
Dělitelé čísla 18 v párech
Obrázek níže zobrazuje dělitele čísla 18 na číselné ose.
Pokud je číslo n náhodou druhou mocninou nějakého celého čísla, pak jedním z dělitelů bude a = b = √n.
▶️ Podívejte se na dělitele čísla 36 v tabulce níže. Protože 36 je druhou mocninou čísla 6, platí a = b = 6 jako jeden z dělitelů. Pro všechny ostatní dvojice dělitelů (a, b) platí a < 6 a b > 6.
Dělitelé čísla 36 v párech
Shrneme-li to:
- Každé číslo n lze zapsat jako n = a x b.
- Pokud je n druhou mocninou čísla, pak a = b = √n.
- Pokud a < b, pak a < √n a b > √n.
- Pokud a > b, pak a > √n a b < √n.
Takže namísto procházení všech celých čísel do n/2 můžeme procházet čísla jen do √n. To je mnohem efektivnější než náš předchozí přístup.
Jak upravit funkci `is_prime()` pro dosažení algoritmu s časovou složitostí O(√n)
Pojďme optimalizovat funkci pro testování prvočísel v Pythonu.
import math
def is_prime(n):
for i in range(2,int(math.sqrt(n))+1):
if (n%i) == 0:
return False
return True
Nyní si analyzujme výše uvedenou definici funkce:
- Pro výpočet druhé odmocniny čísla importujeme vestavěný modul `math` v Pythonu a použijeme funkci `math.sqrt()`.
- Protože n nemusí být druhou mocninou celého čísla, musíme výsledek převést na celé číslo. K převodu `var` na `int` použijeme `int(var)`.
- Abychom zajistili, že skutečně kontrolujeme rozsah až do √n, přidáme k výsledku plus jedna, protože funkce `range()` standardně nezahrnuje koncový bod rozsahu.
Následující blok kódu ověřuje, že naše funkce `is_prime()` funguje správně.
is_prime(8)
# False
is_prime(15)
# False
is_prime(23)
# True
V další části vytvoříme jednoduché grafy, které vizuálně znázorní rozdíl mezi O(n) a O(√n).
Vizuální porovnání O(n) a O(√n)
▶️ Spusťte následující fragment kódu v libovolném prostředí Jupyter notebook.
import numpy as np
import seaborn as sns
import pandas as pd
n = 20
x = np.arange(n)
y1 = np.sqrt(x)
y2 = x
df = pd.DataFrame({"O(√n)":y1,"O(n)":y2})
sns.set_theme()
sns.lineplot(data = df)
Výše uvedený kód ukazuje, jak vykreslit křivky pro n a √n pro daný rozsah hodnot.
- Používáme funkci `numpy.arange()` pro vytvoření pole čísel.
- Poté shromáždíme hodnoty n a √n až do 20 do Pandas DataFrame.
- Nakonec provedeme vykreslení pomocí funkce `seaborn.lineplot()`.
Z grafu níže vidíme, že √n je výrazně menší než n.
Nyní rozšíříme rozsah na 2000 a zopakujeme výše uvedené kroky.
import numpy as np
import seaborn as sns
import pandas as pd
n = 2000
x = np.arange(n)
y1 = np.sqrt(x)
y2 = x
df = pd.DataFrame({"O(√n)":y1,"O(n)":y2})
sns.set_theme()
sns.lineplot(data = df)
Z výše uvedeného grafu můžeme usoudit, že algoritmus s časovou složitostí O(√n) je výrazně rychlejší, když testujeme, zda je velké číslo prvočíslo.
Například: číslo 2377 je prvočíslo – můžete si to sami ověřit! 😀
Zatímco přístup s O(n) by zabral řádově 2000 kroků, algoritmus s O(√n) nám umožní dojít k odpovědi za pouhých 49 kroků.✅
Závěr
⏳ Je čas na rychlé shrnutí.
- Pro zjištění, zda je číslo prvočíslo, je naivní přístup procházet všechna čísla v rozsahu (2, n-1). Pokud nenajdeme dělitele čísla n, pak n je prvočíslo.
- Protože jediným dělitelem n větším než n/2 je samotné n, můžeme procházet pouze do n/2.
- Oba výše uvedené přístupy mají časovou složitost O(n).
- Vzhledem k tomu, že se dělitelé čísel vyskytují v párech, stačí nám procházet čísla pouze do √n. Tento algoritmus je mnohem rychlejší než O(n). Zisk je zvláště patrný při testování, zda je velké číslo prvočíslo.
Doufám, že jste pochopili, jak v Pythonu ověřit, zda je dané číslo prvočíslo. Jako další krok si můžete prohlédnout náš návod na programy v Pythonu pro práci s řetězci – kde se naučíte ověřovat, zda jsou řetězce palindromy, anagramy a další.
Uvidíme se v dalším návodu. Do té doby přeji šťastné kódování! 👩🏽💻