Tento tutoriál vás naučí, jak napsat program Python pro kontrolu, zda je číslo prvočíslo nebo ne.
Pokud jste někdy dělali testy kódování, narazili jste na matematickou otázku v testu na prvočíslo nebo na kontrolu, zda je číslo prvočíslo. A během následujících minut se naučíte přijít na optimální řešení této otázky.
V tomto tutoriálu budete:
- zopakovat si základy prvočísel,
- napište kód Pythonu, abyste zkontrolovali, zda je číslo prvočíslo, a
- optimalizujte jej dále, abyste získali O(√n) runtime algoritmus.
Pro tohle všechno a ještě víc pojďme začít.
Table of Contents
Co je prvočíslo?
Začněme opakováním základů prvočísel.
V teorii čísel se o přirozeném čísle n říká, že je primární pokud má přesně dva faktory: 1 a samotné číslo (n). Vzpomeňte si ze školní matematiky: o číslu i se říká, že je faktorem čísla n, pokud i dělí n rovnoměrně. ✅
Následující tabulka uvádí několik čísel, všechny jejich faktory a pokud jsou prvočísla.
nFactorsIs Prime?11Ne21, 2Ano31, 3Ano41, 2, 4Ne71, 7Ano151, 3, 5, 15Ne
Z výše uvedené tabulky si můžeme zapsat následující:
- 2 je nejmenší prvočíslo.
- 1 je faktorem každého čísla.
- Každé číslo n je faktorem samo o sobě.
Takže 1 a n jsou triviální faktory pro libovolné číslo n. A prvočíslo by nemělo mít žádné jiné faktory než tyto dva.
To znamená, že když přejdete z 2 na n – 1, neměli byste být schopni najít netriviální faktor, který dělí n beze zbytku.
O(n) Algoritmus pro kontrolu, zda je číslo v Pythonu prvočíslo
V této části formalizujme výše uvedený přístup do funkce Pythonu.
Můžete procházet všemi čísly od 2 do n – 1 pomocí objektu range() v Pythonu.
V Pythonu range(start, stop, step) vrací objekt range. Poté můžete iterovat přes objekt range a získat sekvenci od začátku až po konec -1 v krocích.
Protože potřebujeme množinu celých čísel od 2 do n-1, můžeme specifikovat range(2, n) a použít ji ve spojení se smyčkou for.
Zde je to, co bychom chtěli udělat:
- Pokud najdete číslo, které dělí n rovnoměrně beze zbytku, můžete okamžitě dojít k závěru, že číslo není prvočíslo.
- Pokud jste prošli celým rozsahem čísel od 2 až po n – 1, aniž byste našli číslo, které dělí n rovnoměrně, pak je číslo prvočíslo.
Funkce Pythonu pro kontrolu prvočísla
Pomocí výše uvedeného můžeme pokračovat a definovat funkci is_prime() následovně.
def is_prime(n):
for i in range(2,n):
if (n%i) == 0:
return False
return True
Pojďme nyní analyzovat výše uvedenou definici funkce.
- Výše uvedená funkce is_prime() bere jako argument kladné celé číslo n.
- Pokud najdete faktor v určeném rozsahu (2, n-1), funkce vrátí hodnotu False – protože číslo není prvočíslo.
- A vrátí True, pokud projdete celou smyčku bez nalezení faktoru.
Dále zavoláme funkci s argumenty a ověříme, zda je výstup správný.
is_prime(2) # True is_prime(8) # False is_prime(9) # False is_prime(11) # True
Ve výstupu výše vidíte, že 2 a 11 jsou prvočísla (funkce vrací True). A 8 a 9 nejsou prvočísla (funkce vrací False).
Jak optimalizovat funkci Pythonu is_prime()
Zde můžeme provést malou optimalizaci. Dodržujte seznam faktorů v tabulce níže.
NumberFactors61, 2, 3, 6101, 2, 5, 10181, 2, 3, 6, 9, 18
No, vidíme, že jediný faktor n, který je větší než n/2, je n samotné.
To znamená, že nemusíte opakovat celou cestu až do n – 1. Místo toho můžete smyčku spustit pouze do n/2.
Pokud nenajdete netriviální faktor do n/2, nemůžete najít ani jeden za n/2.
Nyní upravme funkci is_prime() pro kontrolu faktorů 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
Pojďme do toho a ověřte výstup pomocí několika volání funkcí.
is_prime(9) # False is_prime(11) # True
I když se může zdát, že jsme optimalizovali, tento algoritmus není efektivnější než předchozí z hlediska komplexnosti běhu. Ve skutečnosti mají oba za běhu O(n) složitost: úměrnou hodnotě n nebo lineární v n.
Můžeme to udělat lépe? Ano, můžeme!
▶️ Pokračujte další částí a zjistěte, jak zlepšit časovou složitost pro testování prvočísel.
O(√n) Algoritmus pro kontrolu prvočísla v Pythonu
Stává se, že činitelé čísla se vyskytují ve dvojicích.
Jestliže a je faktor čísla n, pak existuje také faktor b takový, že axb = n, nebo jednoduše ab = n.
Pojďme si to ověřit na příkladu.
Níže uvedená tabulka ukazuje faktory čísla 18 vyskytující se v párech. Pokud chcete, můžete totéž ověřit pro několik dalších čísel.
Všimněte si také, že √18 je přibližně 4,24.
A ve faktorech, které se vyskytují ve dvojicích (a, b), můžete vidět, že pokud a je menší než 4,24, pak b je větší než 4,24 – v tomto příkladu (2, 18) a (3, 6).
Faktory 18 v párech
Obrázek níže ukazuje faktory 18 vynesené na číselné ose.
Pokud je číslo n náhodou dokonalým čtvercem, budete mít jako jeden z faktorů a = b = √n.
▶️ Podívejte se na faktory 36 v tabulce níže. Protože 36 je dokonalý čtverec, a = b = 6 je jedním z faktorů. Pro všechny ostatní dvojice faktorů (a, b) platí a < 6 ab > 6.
Faktory 36 v párech
Když to shrnu, máme následující:
- Každé číslo n lze zapsat jako n = axb
- Jestliže n je dokonalý čtverec, pak a = b = √n.
- A pokud a < b, pak a < √n a b > √n.
- Jinak, pokud a > b, pak a > √n a b < √n.
Takže místo procházení všech celých čísel až do n/2 můžete zvolit spuštění až do √n. A to je mnohem efektivnější než náš předchozí přístup.
Jak upravit algoritmus is_prime() na O(√n).
Pokračujme optimalizací funkce pro kontrolu 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í pojďme analyzovat výše uvedenou definici funkce:
- Chcete-li vypočítat druhou odmocninu čísla, importujme vestavěný matematický modul Pythonu a použijte funkci math.sqrt().
- Protože n nemusí být dokonalý čtverec, budeme ho muset přehodit na celé číslo. Použijte int(var) k přetypování var na int.
- Abychom se ujistili, že skutečně kontrolujeme až √n, přidáme plus jedna, protože funkce range() ve výchozím nastavení vylučuje koncový bod rozsahu.
Níže uvedená buňka 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 několik jednoduchých grafů, abychom O(n) a O(√n) porozuměli vizuálně.
Vizuální porovnání O(n) a O(√n).
▶️ Spusťte následující fragment kódu v prostředí notebooku Jupyter dle vašeho výběru.
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ý úryvek ukazuje, jak můžete vykreslit křivky pro n a √n pro rozsah hodnot.
- K vytvoření pole čísel používáme funkci NumPy arange().
- A pak shromáždíme hodnoty n a √n až do 20, ale bez toho, do Pandas DataFrame.
- Dále vykreslíme pomocí seaborn’s lineplot() funkce.
Z grafu níže vidíme, že √n je výrazně menší než n.
Nyní zvětšíme rozsah až na 2000 a zopakujeme stejné kroky jako výše.
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ůžete odvodit, že algoritmus O(√n) je výrazně rychlejší, když testujete, zda je velké číslo prvočíslo.
Zde je rychlý příklad: 2377 je prvočíslo – ověřte si to!😀
Zatímco přístup O(n) zabere řádově 2000 kroků, algoritmus O(√n) může pomoci dosáhnout odpovědi v pouhých 49 krocích.✅
Závěr
⏳ A je čas na rychlé shrnutí.
- Chcete-li zkontrolovat, zda je číslo prvočíslo, naivním přístupem je procházet všechna čísla v rozsahu (2, n-1). Pokud nenajdete faktor, který dělí n, pak n je prvočíslo.
- Protože jediným faktorem n větším než n/2 je samotné n, můžete se rozhodnout spustit pouze do n/2.
- Oba výše uvedené přístupy mají časovou složitost O(n).
- Protože faktory čísla se vyskytují ve dvojicích, můžete spustit pouze do √n. Tento algoritmus je mnohem rychlejší než O(n). A zisk je znatelný při kontrole, zda je velké číslo prvočíslo nebo ne.
Doufám, že chápete, jak zkontrolovat, zda je číslo v Pythonu prvočíslo. Jako další krok si můžete prohlédnout náš tutoriál o programech Python o operacích s řetězci – kde se naučíte zkontrolovat, zda jsou řetězce palindromy, anagramy a další.
Uvidíme se v dalším tutoriálu. Do té doby šťastné kódování!👩🏽💻