Count Primes
Lektion 3 von 3 im Kurs Interview-Coding-Challenges – Paket V von Coddy.
Aufgabe
SchwerSchreiben Sie eine Funktion countPrimes, die eine Ganzzahl n erhält und die Anzahl der Primzahlen zurückgibt, die kleiner als n sind.
Hinweis: Die Zeitkomplexität muss besser als O(nlogn) sein.
1 <= n <= 1000000
Beispiele:
Eingabe - 10
Erwartete Ausgabe - 4
Erklärung - Es gibt 4 Primzahlen kleiner als 10: 2, 3, 5, 7
Eingabe - 13
Erwartete Ausgabe - 5
Erklärung - Es gibt 5 Primzahlen kleiner als 13: 2, 3, 5, 7, 11 - beachten Sie, dass 13 nicht mitzählt!
Probier es selbst
int countPrimes(int n) {
// Code hier schreiben
}