Cum verific dacă un număr este prim fără să testez toți divizorii?
Pentru un număr natural mai mare decât 1, este suficient să testezi divizorii primi până la rădăcina pătrată a numărului. Un număr compus are cel puțin un factor în acel interval.
Exemplu explicat
Pentru 97, . Testezi 2,3,5,7; niciunul nu divide 97, deci 97 este prim.
Greșeala de evitat
Include rădăcina când ea este întreagă: pentru 49 trebuie testat 7.
