Testul de primalitate spune că 4, 9 și 25 sunt prime: range(2, int(n ** 0.5)) se oprește prea devreme
range exclude capătul din dreapta, deci range(2, int(n ** 0.5)) nu verifică chiar rădăcina pătrată, iar pătratele numerelor prime (4, 9, 25, 49) trec drept prime. Adaugă +1: range(2, math.isqrt(n) + 1).
Explicat de Tudor Andrei Dumitrescu, Senior Software Developer, fondatorul Academiei ProgramatorilorActualizat la
Ce înseamnă
Ca să verifici dacă n e prim, e suficient să încerci divizorii de la 2 până la √n inclusiv: dacă n are un divizor mai mare decât √n, are și unul mai mic. Cuvântul important e inclusiv.
range(a, b) se oprește înainte de b. Pentru n = 9, int(9 ** 0.5) e 3, iar range(2, 3) încearcă doar divizorul 2. Cum 9 nu se împarte la 2, funcția spune că 9 e prim. La fel pentru 4 (range(2, 2) e gol), 25, 49 și orice pătrat al unui număr prim. Restul numerelor ies corect, așa că greșeala trece de testele cu numere mici luate la întâmplare.
math.isqrt(n) dă partea întreagă exactă a radicalului, fără erorile de rotunjire ale lui n ** 0.5 la numere mari, iar + 1 include radicalul în verificare.
De ce apare: cauzele frecvente
1Limita superioară exclusă
for d in range(2, int(n ** 0.5)):
if n % d == 0:
return Falsefor d in range(2, math.isqrt(n) + 1):
if n % d == 0:
return FalseCu + 1, bucla verifică și d = √n, adică exact divizorul care lipsea la pătratele perfecte.
2Ciurul lui Eratostene fără ultimul număr
prim = [True] * n
for i in range(2, n):
...prim = [True] * (n + 1)
for i in range(2, n + 1):
...Dacă vrei numerele prime până la n inclusiv, lista și bucla trebuie să ajungă la indicele n.
3Cazurile 0 și 1
def e_prim(n):
for d in range(2, math.isqrt(n) + 1):
...
return Truedef e_prim(n):
if n < 2:
return False
for d in range(2, math.isqrt(n) + 1):
...
return True0 și 1 nu sunt prime, dar bucla nu face niciun pas pentru ele și funcția ar returna True.
Repară eroarea, direct în pagină
Funcția e_prim(n) verifică dacă un număr e prim. Testul cu assert pică: lista numerelor prime mai mici decât 30 conține și 4, 9 și 25. Repar-o ca să afișeze [2, 3, 5, 7, 11, 13, 17, 19, 23, 29].
def e_prim(n):
if n < 2:
return False
for d in range(2, int(n ** 0.5)):
if n % d == 0:
return False
return True
prime = [n for n in range(30) if e_prim(n)]
assert prime == [2, 3, 5, 7, 11, 13, 17, 19, 23, 29], f'prime gresite: {prime}'
print(prime)[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
Indiciu
Bucla trebuie să verifice și divizorul egal cu radicalul lui n.
Reparația
import math
def e_prim(n):
if n < 2:
return False
for d in range(2, math.isqrt(n) + 1):
if n % d == 0:
return False
return True
prime = [n for n in range(30) if e_prim(n)]
assert prime == [2, 3, 5, 7, 11, 13, 17, 19, 23, 29], f'prime gresite: {prime}'
print(prime)De ce merge
Pentru 9, int(9 ** 0.5) e 3, iar range(2, 3) încerca doar divizorul 2, deci 3 nu era verificat. Pentru 4, range(2, 2) era complet gol. Cu math.isqrt(n) + 1, bucla merge până la radical inclusiv: 9 se împarte la 3, 4 la 2, 25 la 5, deci sunt respinse. Celelalte numere prime nu au niciun divizor până la radical, așa că rămân în listă.
Cum o eviți pe viitor
Testează orice funcție de primalitate pe pătratele numerelor prime (4, 9, 25, 49) și pe 0, 1, 2. Compară lista de numere prime sub 30 cu cea cunoscută: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29. Când o limită trebuie inclusă, scrie + 1 lângă ea și citește condiția cu voce tare („până la radical, inclusiv”).
Întrebări frecvente
De ce math.isqrt și nu int(n ** 0.5)?
n ** 0.5 trece prin float, care are precizie limitată. Pentru numere de peste aproximativ 15 cifre, rezultatul poate fi cu 1 mai mic decât radicalul real. math.isqrt lucrează exact, cu întregi.
E suficient să încerc doar divizorii impari?
Da, după ce verifici separat 2: range(3, math.isqrt(n) + 1, 2). Reduce numărul de pași la jumătate.
Erori înrudite
Fereastra glisantă sare peste ultima fereastră (off-by-one la range) O listă cu n elemente are n - k + 1 ferestre de lungime k, deci bucla trebuie să fie range(len(lista) - k + 1). Cu range(len(lista) - k) ultima fereastră nu e verificată, iar rezultatul e greșit fără nicio eroare. Bucla inversă range(len(nums) - 1, 0, -1) sare peste primul element range se oprește înainte de valoarea stop, deci range(n - 1, 0, -1) se termină la 1 și nu ajunge la indexul 0. Pentru a parcurge toți indicii de la coadă scrie range(len(nums) - 1, -1, -1) sau reversed(range(len(nums))). OverflowError: int too large to convert to float Un întreg Python poate fi oricât de mare, dar un float nu trece de aproximativ 1.8e308, iar math.sqrt, / sau float() încearcă să-l transforme. Rămâi în întregi: math.isqrt(n) pentru radical, // pentru împărțire, comparații între întregi. Învață Algoritmi și structuri de date de la zero, cu exerciții la fiecare lecție
Curs Algoritmi pentru interviuri: lecții scurte, fiecare cu un exercițiu verificat automat, direct în browser. Primele 2 lecții sunt gratuite.
