...
Eroare Algoritmi și structuri de date · Numere, biți și caractere

Testul de primalitate spune că 4, 9 și 25 sunt prime: range(2, int(n ** 0.5)) se oprește prea devreme

Pe scurt

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ă

Greșit
PYTHON
for d in range(2, int(n ** 0.5)):
    if n % d == 0:
        return False
Corect
PYTHON
for d in range(2, math.isqrt(n) + 1):
    if n % d == 0:
        return False

Cu + 1, bucla verifică și d = √n, adică exact divizorul care lipsea la pătratele perfecte.

2Ciurul lui Eratostene fără ultimul număr

Greșit
PYTHON
prim = [True] * n
for i in range(2, n):
    ...
Corect
PYTHON
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

Greșit
PYTHON
def e_prim(n):
    for d in range(2, math.isqrt(n) + 1):
        ...
    return True
Corect
PYTHON
def e_prim(n):
    if n < 2:
        return False
    for d in range(2, math.isqrt(n) + 1):
        ...
    return True

0 și 1 nu sunt prime, dar bucla nu face niciun pas pentru ele și funcția ar returna True.

Repară tu

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

Codul care dă eroarea
PYTHON
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)
După reparație, programul afișează
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
Indiciu

Bucla trebuie să verifice și divizorul egal cu radicalul lui n.

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

← Toate erorile Algoritmi și structuri de date

Tudor Andrei Dumitrescu
Cine a explicat eroarea

Tudor Andrei Dumitrescu

Senior Software Developer · fondatorul Academiei Programatorilor

LinkedIn
  1. 2019 Junior JavaCognizant Softvision
  2. 2021 Mid JavaCognizant Softvision
  3. 2022 Team LeaderEndava
  4. 2023 Senior Software DeveloperUniCredit
  5. Acum Senior Software DeveloperHCLTech
Certificat de absolvire Instructor / Preparator formare, Tudor Andrei Dumitrescu
Certificat de formator autorizatMinisterul Muncii și Ministerul Educației · 2022
Certificat de absolvire Instructor / Preparator formare, Tudor Andrei Dumitrescu

Certificat de formator autorizat · Ministerul Muncii și Ministerul Educației · 2022

Din 2020 construiește Academia Programatorilor, iar din 2026 și JoburiIT.ro. Fiecare eroare de aici a fost reprodusă în editorul nostru: codul greșit chiar dă mesajul din titlu, iar reparația chiar funcționează.

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