Acest tutorial vă va învăța cum să scrieți un program Python pentru a verifica dacă un număr este prim sau nu.
Dacă ați susținut vreodată teste de codificare, veți fi întâlnit cu întrebarea de matematică la testul pentru primalitate sau pentru a verifica dacă un număr este prim. Și în următoarele câteva minute, veți învăța să veniți cu soluția optimă la această întrebare.
În acest tutorial, veți:
- revizuiește elementele de bază ale numerelor prime,
- scrie codul Python pentru a verifica dacă un număr este prim și
- optimizați-l în continuare pentru a obține un algoritm de rulare O(√n).
Pentru toate acestea și multe altele, să începem.
Cuprins
Ce este un număr prim?
Să începem prin a revizui elementele de bază ale numerelor prime.
În teoria numerelor, un număr natural n se spune că este prim dacă are exact doi factori: 1 și numărul însuși (n). Amintiți-vă din matematica de la școală: se spune că un număr i este un factor al numărului n, dacă i împarte n egal. ✅
Următorul tabel listează câteva numere, toți factorii lor și dacă sunt prime.
nFactorsIs Prime?11Nu21, 2Da31, 3Da41, 2, 4Nu71, 7Da151, 3, 5, 15Nu
Din tabelul de mai sus, putem nota următoarele:
- 2 este cel mai mic număr prim.
- 1 este un factor al fiecărui număr.
- Fiecare număr n este un factor al sinelui.
Deci 1 și n sunt factori banali pentru orice număr n. Și un număr prim nu ar trebui să aibă alți factori decât acești doi.
Aceasta înseamnă că atunci când treceți de la 2 la n – 1, nu ar trebui să puteți găsi un factor netrivial care să împartă n fără rest.
O(n) Algoritm pentru a verifica dacă un număr este prim în Python
În această secțiune, să formalizăm abordarea de mai sus într-o funcție Python.
Puteți parcurge toate numerele de la 2 la n – 1 folosind obiectul range() din Python.
În Python, range(start, stop, step) returnează un obiect range. Apoi puteți itera pe obiectul interval pentru a obține o secvență de la început până la oprire -1 în pași de pas.
Deoarece avem nevoie de mulțimea de numere întregi de la 2 la n-1, putem specifica intervalul (2, n) și îl putem folosi împreună cu bucla for.
Iată ce ne-am dori să facem:
- Dacă găsiți un număr care împarte n uniform fără rest, puteți concluziona imediat că numărul nu este prim.
- Dacă ați parcurs întregul interval de numere de la 2 până la n – 1 fără a găsi un număr care să împartă n uniform, atunci numărul este prim.
Funcția Python pentru a verifica numărul prim
Folosind cele de mai sus, putem continua și defini funcția is_prime() după cum urmează.
def is_prime(n):
for i in range(2,n):
if (n%i) == 0:
return False
return True
Să analizăm acum definiția funcției de mai sus.
- Funcția de mai sus is_prime() ia ca argument un întreg pozitiv n.
- Dacă găsiți un factor în intervalul specificat de (2, n-1), funcția returnează False, deoarece numărul nu este prim.
- Și returnează True dacă parcurgeți întreaga buclă fără a găsi un factor.
Apoi, să apelăm funcția cu argumente și să verificăm dacă rezultatul este corect.
is_prime(2) # True is_prime(8) # False is_prime(9) # False is_prime(11) # True
În rezultatul de mai sus, vedeți că 2 și 11 sunt prime (funcția returnează True). Și 8 și 9 nu sunt prime (funcția returnează False).
Cum să optimizați funcția Python is_prime()
Putem face o mică optimizare aici. Observați lista de factori din tabelul de mai jos.
NumberFactors61, 2, 3, 6101, 2, 5, 10181, 2, 3, 6, 9, 18
Ei bine, putem vedea că singurul factor al lui n care este mai mare decât n/2 este n însuși.
Deci, aceasta înseamnă că nu trebuie să faceți o buclă până la n – 1. În schimb, puteți rula bucla numai până la n/2.
Dacă nu găsiți un factor non-trivial până la n/2, nu puteți găsi nici unul dincolo de n/2.
Acum să modificăm funcția is_prime() pentru a verifica factorii din intervalul (2, n/2)
def is_prime(n):
for i in range(2,int(n/2)):
if (n%i) == 0:
return False
return True
Să mergem mai departe și să verificăm rezultatul prin câteva apeluri de funcție.
is_prime(9) # False is_prime(11) # True
Chiar dacă pare că am optimizat, acest algoritm nu este mai eficient decât precedentul în ceea ce privește complexitatea timpului de execuție. De fapt, ambele au o complexitate de rulare O(n): proporțională cu valoarea lui n sau liniară în n.
Putem face mai bine? Da putem!
▶️ Treceți la următoarea secțiune pentru a determina cum să îmbunătățiți complexitatea timpului pentru testarea numerelor prime.
O(√n) Algoritm pentru a verifica numărul prim în Python
Se întâmplă ca factorii unui număr să apară în perechi.
Dacă a este un factor al numărului n, atunci există și un factor b astfel încât axb = n, sau pur și simplu, ab = n.
Să verificăm acest lucru printr-un exemplu.
Tabelul de mai jos arată factorii numărului 18 care apar în perechi. Puteți verifica același lucru pentru câteva numere, dacă doriți.
De asemenea, rețineți că √18 este aproximativ 4,24.
Și în factorii care apar în perechi (a, b), puteți vedea că dacă a este mai mic de 4,24, atunci b este mai mare decât 4,24 – în acest exemplu, (2, 18) și (3, 6).
Factori de 18 în perechi
Figura de mai jos arată factorii lui 18 reprezentați pe linia numerică.
Dacă numărul n se întâmplă să fie un pătrat perfect, veți avea ca unul dintre factori a = b = √n.
▶️ Priviți factorii lui 36 din tabelul de mai jos. Deoarece 36 este un pătrat perfect, a = b = 6 este unul dintre factori. Pentru toate celelalte perechi de factori (a, b), a < 6 și b > 6 este valabil.
Factori de 36 în perechi
Rezumând, avem următoarele:
- Fiecare număr n poate fi scris ca n = axb
- Dacă n este un pătrat perfect, atunci a = b = √n.
- Și dacă a < b, atunci, a < √n și b > √n.
- Altfel, dacă a > b, atunci a > √n și b < √n.
Deci, în loc să treceți în buclă prin toate numerele întregi până la n/2, puteți alege să rulați până la √n. Și aceasta este mult mai eficientă decât abordarea noastră anterioară.
Cum se modifică algoritmul is_prime() la O(√n).
Să continuăm cu optimizarea funcției pentru a verifica numerele prime în Python.
import math
def is_prime(n):
for i in range(2,int(math.sqrt(n))+1):
if (n%i) == 0:
return False
return True
Acum, să analizăm definiția funcției de mai sus:
- Pentru a calcula rădăcina pătrată a unui număr, să importăm modulul matematic încorporat din Python și să folosim funcția math.sqrt().
- Deoarece n poate să nu fie un pătrat perfect, va trebui să-l transformăm într-un număr întreg. Utilizați int(var) pentru a transforma var într-un int.
- Pentru a ne asigura că verificăm de fapt până la √n, adăugăm un plus unu deoarece funcția range() exclude punctul final al intervalului în mod implicit.
Celula de cod de mai jos verifică dacă funcția noastră is_prime() funcționează corect.
is_prime(8) # False is_prime(15) # False is_prime(23) # True
În secțiunea următoare, să creăm câteva diagrame simple pentru a înțelege vizual O(n) și O(√n).
Comparând O(n) și O(√n) vizual
▶️ Rulați următorul fragment de cod într-un mediu de notebook Jupyter la alegere.
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)
Fragmentul de mai sus arată cum puteți trasa curbele pentru n și √n pentru un interval de valori.
- Folosim funcția NumPy arange() pentru a crea o matrice de numere.
- Și apoi, colectăm valorile lui n și √n până la, dar fără a include 20, într-un panda DataFrame.
- În continuare, complotăm folosind graficul seaborn () funcţie.
Din graficul de mai jos, vedem că √n este semnificativ mai mic decât n.
Acum să creștem intervalul până la 2000 și să repetăm aceiași pași ca mai sus.
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)
Din graficul de mai sus, puteți deduce că algoritmul O(√n) este semnificativ mai rapid atunci când testați dacă un număr mare este prim.
Iată un exemplu rapid: 2377 este un număr prim – verificați acest lucru!😀
În timp ce abordarea O(n) va lua ordinul a 2000 de pași, algoritmul O(√n) poate ajuta la obținerea răspunsului în doar 49 de pași.✅
Concluzie
⏳ Și este timpul pentru un rezumat rapid.
- Pentru a verifica dacă un număr este prim, abordarea naivă este să faci bucla prin toate numerele din intervalul (2, n-1). Dacă nu găsiți un factor care împarte n, atunci n este prim.
- Deoarece singurul factor de n mai mare decât n/2 este n însuși, puteți alege să rulați numai până la n/2.
- Ambele abordări de mai sus au o complexitate de timp de O(n).
- Deoarece factorii unui număr apar în perechi, puteți rula doar până la √n. Acest algoritm este mult mai rapid decât O(n). Iar câștigul este apreciabil atunci când se verifică dacă un număr mare este prim sau nu.
Sper că înțelegeți cum să verificați dacă un număr este prim în Python. Ca pas următor, puteți consulta tutorialul nostru despre programele Python despre operațiile cu șiruri, unde veți învăța să verificați dacă șirurile sunt palindrome, anagrame și multe altele.
Ne vedem cu toții într-un alt tutorial. Până atunci, codare fericită!👩🏽💻