jeśli spędziłeś trochę czasu na wojnach kodowych, znalezienie liczby pierwszej jest częstym tematem wśród kategorii problemów. Kiedy zacząłem kodować, pomyślałem, że zapętlenie wszystkich liczb od 1 do num i sprawdzenie, czy są podzielne, było świetnym podejściem. Jednak, jak tylko dowiedziałem się o big o notation byłem zawstydzony!

po kilku badaniach i czytaniu wiki w ten weekend, znalazłem świetną funkcję do znajdowania, czy liczba jest pierwsza z czasem podliniowym O(n). Poniższa funkcja jest rozwiązaniem, które znalazłem:

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. sprawdza, czy liczba jest 0, 1 lub ujemna. Zwracanie true, jeśli liczba mieści się w tym zakresie.
  2. sprawdza, czy liczba jest 2 lub 3. Zwracanie true, jeśli liczba jest 2 lub 3.
  3. ostatnie polecenie if zwraca, że liczba nie jest pierwsza, jeśli jest podzielna przez 2 lub 3.
  4. ostatnia część tej funkcji jest najtrudniejsza-pętla while! Zasadniczo sprawdza każdą nieparzystą liczbę, która nie jest podzielna przez 3, dopóki nie stanie się większa niż pierwiastek kwadratowy liczby. Na przykład, pierwszy i i i + 2 będzie 5 i 7. Następne i i i + 2 będą 11 i 13. Nie sprawdza 9 ani 15, ponieważ oba są podzielne przez 3 i zostałyby złapane w ostatniej instrukcji else if.
  5. w końcu zwraca true, jeśli liczba nie była podzielna przez jakiekolwiek wpisy i lub i+2, ponieważ liczba jest pierwsza.

O(N)

jeśli założymy, że n jest liczbą przekazaną do isPrime, O(N) mojego początkowego podejścia byłoby O(N). Zatem złożoność czasowa byłaby liniowa. Jest to w porządku, jeśli wszystko, co robisz, to sprawdzanie, ale wiele razy ta funkcja jest funkcją pomocniczą i sprawdzanie, czy lista liczb jest pierwsza, byłoby wykładnicze.

powyższa funkcja isPrime byłaby O (N^1/2). Oznacza to, że złożoność czasowa będzie podliniowa, co znacznie zmniejszy złożoność czasową większej funkcji.

Na Zakończenie