als je tijd hebt besteed aan code oorlogen, het vinden van een getal is prime is een gemeenschappelijk thema onder een categorie van problemen. Toen ik voor het eerst begon met coderen dacht ik dat looping door alle nummers 1 tot num en controleren of het deelbaar was een geweldige aanpak was. Echter, zodra ik hoorde over big O notatie ik was vernederd!

na wat onderzoek en wiki lezen dit weekend, vond ik een geweldige functie om te vinden of een getal priemgetal is met een sub-lineaire o(n) tijd. De volgende functie is de oplossing die ik vond:

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. controleert of het getal 0, 1 of negatief is. true retourneren als het getal binnen dit bereik ligt.
  2. controleert of het getal 2 of 3 is. Geeft true terug als het nummer 2 of 3 is.
  3. Het Laatste if statement geeft aan dat het getal geen priemgetal is als het deelbaar is door 2 of 3.
  4. het laatste deel van deze functie is het lastigste-de while-lus! Het is in wezen het controleren van elk oneven getal dat niet deelbaar is door 3 totdat het groter wordt dan de vierkantswortel van het num. De eerste i en i + 2 zijn bijvoorbeeld 5 en 7. De volgende i en i + 2 worden 11 en 13. Het controleert niet 9 of 15 omdat beide deelbaar zijn door 3 en zouden zijn gevangen in het laatste else if statement.
  5. geeft uiteindelijk true terug als het getal niet deelbaar was door een i of i+2 item omdat het getal een priemgetal is.

O(n)

als we aannemen dat n het getal is dat in isPrime is doorgegeven, zou de o(n) van mijn initiële benadering O (n) zijn. Daarom zou deze tijd complexiteit lineair zijn. Dit is prima als alles wat je doet is de check, maar vaak is deze functie een helper functie en het controleren of een lijst met getallen priemgetallen is zou exponentieel zijn.

de bovenstaande functie isPrime zou O(n^1/2) zijn. Dit betekent dat de tijdcomplexiteit sub-lineair zal zijn, wat de tijdcomplexiteit van een grotere functie sterk zal verminderen.

Concluderend