Se hai passato del tempo a guerre di codice, trovare se un numero è primo è un tema comune tra una categoria di problemi. Quando ho iniziato a codificare, ho pensato che scorrere tutti i numeri da 1 a num e verificare se fosse divisibile fosse un ottimo approccio. Tuttavia, non appena ho saputo della notazione big O sono rimasto mortificato!

Dopo alcune ricerche e la lettura wiki di questo fine settimana, ho trovato una grande funzione per trovare se un numero è primo con un tempo O(n) sub-lineare. La seguente funzione è la soluzione che ho trovato:

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. Controlla se il numero è 0, 1 o negativo. Restituendo true se il numero è all’interno di questo intervallo.
  2. Controlla se il numero è 2 o 3. Restituendo true se il numero è 2 o 3.
  3. L’ultima istruzione if restituisce che il numero non è primo se è divisibile per 2 o 3.
  4. L’ultima parte di questa funzione è la più complicata: il ciclo while! Sta essenzialmente controllando ogni numero dispari che non è divisibile per 3 finché non diventa più grande della radice quadrata del numero. Ad esempio, i primi i e i + 2 saranno 5 e 7. I prossimi i e i + 2 saranno 11 e 13. Non controlla 9 o 15 perché entrambi sono divisibili per 3 e sarebbero stati catturati nell’ultima istruzione else if.
  5. Restituisce infine true se il numero non era divisibile per nessuna voce i o i+2 perché il numero è primo.

O(n)

Se assumiamo che n sia il numero passato in isPrime, l’O(n) del mio approccio iniziale sarebbe O(n). Pertanto, questa volta la complessità sarebbe lineare. Questo va bene se tutto ciò che stai facendo è il controllo, ma molte volte questa funzione è una funzione di supporto e controllare se un elenco di numeri è primo sarebbe esponenziale.

La funzione di cui sopra isPrime sarebbe O (n^1/2). Ciò significa che la complessità temporale sarà sub-lineare, il che ridurrà notevolmente la complessità temporale di una funzione più grande.

In conclusione