Wenn Sie Zeit mit Codekriegen verbracht haben, ist es ein häufiges Thema in einer Kategorie von Problemen, herauszufinden, ob eine Zahl eine Primzahl ist. Als ich mit dem Codieren anfing, dachte ich, es sei ein großartiger Ansatz, alle Zahlen von 1 bis num zu durchlaufen und zu überprüfen, ob sie teilbar sind. Sobald ich jedoch von der Big O-Notation erfuhr, war ich beschämt!

Nach einigen Recherchen und Wiki-Lektüre an diesem Wochenende fand ich eine großartige Funktion, um herauszufinden, ob eine Zahl eine Primzahl mit einer sublinearen O (n) -Zeit ist. Die folgende Funktion ist die Lösung, die ich gefunden habe:

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. Prüft, ob die Zahl 0, 1 oder negativ ist. Rückgabe von true, wenn die Zahl innerhalb dieses Bereichs liegt.
  2. Prüft, ob die Zahl 2 oder 3 ist. Gibt true zurück, wenn die Zahl 2 oder 3 ist.
  3. Die letzte if -Anweisung gibt zurück, dass die Zahl keine Primzahl ist, wenn sie durch 2 oder 3 teilbar ist.
  4. Der letzte Teil dieser Funktion ist der schwierigste – die while-Schleife! Es überprüft im Wesentlichen jede ungerade Zahl, die nicht durch 3 teilbar ist, bis sie größer als die Quadratwurzel der Zahl wird. Zum Beispiel sind die ersten i und i + 2 5 und 7. Die nächsten i und i + 2 werden 11 und 13 sein. Es überprüft nicht 9 oder 15, da beide durch 3 teilbar sind und in der letzten else if -Anweisung abgefangen worden wären.
  5. gibt schließlich truezurück, wenn die Zahl nicht durch i oder i+2 Einträge teilbar war, da die Zahl Primzahl ist.

O(n)

Wenn wir annehmen, dass n die an isPrime übergebene Zahl ist, wäre das O(n) meines anfänglichen Ansatzes O(n). Daher wäre diese Zeitkomplexität linear. Dies ist in Ordnung, wenn Sie nur die Überprüfung durchführen, aber oft ist diese Funktion eine Hilfsfunktion, und die Überprüfung, ob eine Liste von Zahlen Primzahlen ist, wäre exponentiell.

Die obige Funktion isPrime wäre O(n ^1/2). Dies bedeutet, dass die Zeitkomplexität sublinear ist, was die Zeitkomplexität einer größeren Funktion stark verringert.

Abschließend