ha időt töltött a kódháborúkkal, annak megállapítása, hogy egy szám elsődleges-e, a problémák egy kategóriája között gyakori téma. Amikor először elkezdtem kódolni, azt gondoltam, hogy az összes 1-es számot a num-ra hurkolni, és ellenőrizni, hogy osztható-e, nagyszerű megközelítés volt. Azonban, amint megtudtam a nagy O jelölésről, megaláztam!

némi kutatás és wiki olvasás után ezen a hétvégén találtam egy nagyszerű funkciót annak megállapítására, hogy egy szám prímszám-e szublináris o(n) idővel. A következő funkció a megoldás, amit találtam:

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. ellenőrzi, hogy a szám 0, 1 vagy negatív-e. Visszatérés true ha a szám ezen a tartományon belül van.
  2. ellenőrzi, hogy a szám 2 vagy 3. Visszatérés true ha a szám 2 vagy 3.
  3. az utolsó if állítás azt adja vissza, hogy a szám nem prím, ha osztható 2-vel vagy 3-mal.
  4. ennek a funkciónak az utolsó része a legbonyolultabb — a while hurok! Lényegében minden olyan páratlan számot ellenőriz, amely nem osztható 3-mal, amíg nagyobb lesz, mint a szám négyzetgyöke. Például az első i és i + 2 5 és 7 lesz. A következő i és i + 2 11 és 13 lesz. Nem ellenőrzi a 9-et vagy a 15-öt, mert mindkettő osztható 3-mal, és az utolsó else if utasításba került volna.
  5. végül true értéket ad vissza, ha a szám nem osztható egyetlen i vagy i+2 bejegyzéssel sem, mert a szám prím.

O(n)

ha feltételezzük, hogy n az isPrime-be átadott szám, akkor a kezdeti megközelítésem O(n) lenne O(n). Ezért ezúttal a komplexitás lineáris lenne. Ez rendben van, ha csak az ellenőrzést végzi, de sokszor ez a funkció segítő funkció, és annak ellenőrzése, hogy a számok listája elsődleges-e, exponenciális lenne.

a fenti isPrime függvény O(n^1/2) lenne. Ez azt jelenti, hogy az idő bonyolultsága szublináris lesz, ami nagymértékben csökkenti egy nagyobb függvény idő bonyolultságát.

Összefoglalva