dacă ați petrecut orice moment pe code wars, găsirea dacă un număr este prim este o temă comună într-o categorie de probleme. Când am început de codificare am crezut looping prin toate numerele 1 la num și verificarea dacă a fost divizibil a fost o abordare mare. Cu toate acestea, de îndată ce am aflat despre notația big O, am fost mortificat!

după câteva cercetări și lecturi wiki în acest weekend, am găsit o funcție excelentă pentru a afla dacă un număr este prim cu un timp o(n) sub-liniar. Următoarea funcție este soluția pe care am găsit-o:

function isPrime (num) {
if (num <= 1) {
return true
} else if (num <= 3) {
return true
} else if (num%2 === 0 || num%3 === 0) {
return false
}
let i = 5
while (i*i <= num) {
if (num%i === 0 || num%(i+2) === 0) {
return false
}
i += 6
}
return true
}
  1. verifică dacă numărul este 0, 1 sau negativ. Revenind true dacă numărul este în acest interval.
  2. verifică dacă numărul este 2 sau 3. Revenind true dacă numărul este 2 sau 3.
  3. ultima declarație if returnează că numărul nu este prim dacă este divizibil cu 2 sau 3.
  4. ultima parte a acestei funcții este cea mai dificilă — bucla while! În esență, verifică fiecare număr impar care nu este divizibil cu 3 până când devine mai mare decât rădăcina pătrată a num. De exemplu, primele i și i + 2 vor fi 5 și 7. Următoarele i și i + 2 vor fi 11 și 13. Nu verifică 9 sau 15, deoarece ambele sunt divizibile cu 3 și ar fi fost surprinse în ultima afirmație else if.
  5. returnează în cele din urmă true dacă numărul nu a fost divizibil cu nicio intrare i sau i+2, deoarece numărul este prim.

O(n)

dacă presupunem că n este numărul trecut în isPrime, O(n) din abordarea mea inițială ar fi O(n). Prin urmare, această complexitate de timp ar fi liniară. Acest lucru este bine dacă tot ce faceți este verificarea, dar de multe ori această funcție este o funcție de ajutor și verificarea dacă o listă de numere este prim ar fi exponențială.

funcția de mai sus isPrime ar fi O(n^1/2). Aceasta înseamnă că complexitatea timpului va fi subliniară, ceea ce va reduce foarte mult complexitatea timpului unei funcții mai mari.

În Concluzie