om du har tillbringat någon tid på kod krig, hitta om ett nummer är prime är ett vanligt tema bland en kategori av problem. När jag först började koda trodde jag att looping genom alla nummer 1 till num och kontrollera om det var delbart var ett bra tillvägagångssätt. Men så snart jag lärde mig om big O notation blev jag dödad!

efter lite forskning och wiki-läsning i helgen hittade jag en bra funktion för att hitta om ett tal är prime med en sublinjär O(n) tid. Följande funktion är lösningen jag hittade:

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. kontrollerar om siffran är 0, 1 eller negativ. Returnerar true om numret ligger inom detta intervall.
  2. kontrollerar om siffran är 2 eller 3. Returnerar true om siffran är 2 eller 3.
  3. den sista if – satsen returnerar att numret inte är prime om det är delbart med 2 eller 3.
  4. den sista delen av denna funktion är den svåraste-While loop! Det kontrollerar i huvudsak varje udda tal som inte är delbart med 3 tills det blir större än kvadratroten av num. Till exempel kommer den första i och i + 2 att vara 5 och 7. Nästa i och i + 2 kommer att vara 11 och 13. Det kontrollerar inte 9 eller 15 eftersom båda är delbara med 3 och skulle ha fångats i det sista else if – uttalandet.
  5. returnerar slutligen true om numret inte var delbart med några i eller i+2 – poster eftersom numret är prime.

O(n)

om vi antar att n är numret som överförs till isPrime, skulle O(n) av min ursprungliga inställning vara O (n). Därför skulle denna tidskomplexitet vara linjär. Det här är bra om allt du gör är kontrollen, men många gånger är den här funktionen en hjälpfunktion och att kontrollera om en lista med siffror är prime skulle vara exponentiell.

ovanstående funktion isPrime skulle vara O(n^1/2). Detta innebär att tidskomplexiteten kommer att vara sublinjär, vilket kraftigt minskar tidskomplexiteten hos en större funktion.

Sammanfattningsvis