Contare i numeri primi

Lezione 3 di 3 del corso Sfide di programmazione per colloqui - Pacchetto V di Coddy.

Sfida

Difficile

Scrivi una funzione countPrimes che riceve un numero intero n e restituisce il numero di numeri primi minori di n.

Nota: la complessità temporale deve essere migliore di O(nlogn)

1 <= n <= 1000000

Esempi:

Input - 10

Output previsto - 4

Spiegazione - Ci sono 4 numeri primi minori di 10: 2, 3, 5, 7

Input - 13

Output previsto - 5

Spiegazione - Ci sono 5 numeri primi minori di 13: 2, 3, 5, 7, 11 - nota che 13 non conta!

Provalo tu

int countPrimes(int n) {
    // Scrivi il codice qui
}

Tutte le lezioni di Sfide di programmazione per colloqui - Pacchetto V

1Sfide