pokud jste strávili nějaký čas na kódových válkách, zjištění, zda je číslo prvočíslo, je běžným tématem mezi kategoriemi problémů. Když jsem poprvé začal kódovat, myslel jsem, že opakování všech čísel 1 na num a kontrola, zda je dělitelné, je skvělý přístup. Jakmile jsem se však dozvěděl o notaci big O, byl jsem ponížen!

po nějakém výzkumu a čtení wiki tento víkend jsem našel skvělou funkci pro zjištění, zda je číslo prvočíslo s sublineárním časem O(n). Následující funkce je řešení, které jsem našel:

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. zkontroluje, zda je číslo 0, 1 nebo záporné. Vrací true, pokud je číslo v tomto rozsahu.
  2. zkontroluje, zda je číslo 2 nebo 3. Vrací true, pokud je číslo 2 nebo 3.
  3. poslední příkaz if vrací, že číslo není prvočíslo, pokud je dělitelné 2 nebo 3.
  4. poslední část této funkce je nejsložitější-smyčka while! V podstatě kontroluje každé liché číslo, které není dělitelné 3, dokud se nestane větší než druhá odmocnina čísla. Například první i a i + 2 bude 5 a 7. Další i a i + 2 budou 11 a 13. Nekontroluje 9 nebo 15, protože oba jsou dělitelné 3 a byly by zachyceny v posledním příkazu else if.
  5. nakonec vrátí true , pokud číslo nebylo dělitelné žádnými položkami i nebo i+2, protože číslo je prvočíslo.

O(n)

pokud předpokládáme, že n je číslo předané do isPrime, O(n) mého počátečního přístupu by bylo O (n). Proto by tato časová složitost byla lineární. To je v pořádku, pokud vše, co děláte, je kontrola, ale mnohokrát je tato funkce pomocnou funkcí a kontrola, zda je seznam čísel prvočíselný, by byla exponenciální.

výše uvedená funkce isPrime by byla O (n^1/2). To znamená, že časová složitost bude sublineární, což výrazně sníží časovou složitost větší funkce.

Na Závěr