Hvis du har brukt noe tid på kode kriger, finne hvis et tall er prime er et vanlig tema blant en kategori av problemer. Da jeg først begynte koding trodde jeg looping gjennom alle tall 1 til num og sjekke om det var delelig var en god tilnærming. Men så snart jeg lærte om big o notasjon, ble jeg mortified!

etter litt forskning og wiki-lesing denne helgen fant jeg en flott funksjon for å finne om et tall er prime med en sub-lineær O(n) tid. Følgende funksjon er løsningen jeg fant:

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. Kontrollerer om tallet er 0, 1 eller negativt. Returnerer true hvis nummeret er innenfor dette området.
  2. Kontrollerer om tallet er 2 eller 3. Returnerer true hvis tallet er 2 eller 3.
  3. den siste if setningen returnerer at tallet ikke er primtall hvis det er delbart med 2 eller 3.
  4. den siste delen av denne funksjonen er den vanskeligste-the while loop! Det er i hovedsak å sjekke hvert oddetall som ikke er delbart med 3 til det blir større enn kvadratroten av numet. For eksempel vil den første i og i + 2 være 5 og 7. Den neste i og i + 2 blir 11 og 13. Det kontrollerer ikke 9 eller 15 fordi begge er delbare med 3 og ville ha blitt fanget i den siste else if setningen.
  5. returnerer Endelig true hvis tallet ikke var delbart med noen i eller i+2 oppføringer fordi tallet er primtall.

O(n)

hvis vi antar at n er tallet som er gått inn I isPrime, Vil o(n) av min første tilnærming Være O (n). Derfor vil denne gangen kompleksiteten være lineær. Dette er greit hvis alt du gjør er sjekken, men mange ganger denne funksjonen er en hjelpefunksjon og sjekke om en liste over tall er prime ville være eksponentiell.

funksjonen ovenfor isPrime ville Være O(n^1/2). Dette betyr at tidskompleksiteten vil være sub-lineær, noe som i stor grad vil redusere tidskompleksiteten til en større funksjon.

Som Konklusjon