Problem
Wie viele Primzahlen gibt es von 1 bis 100? Und wie viele von 50 bis 60? Zähle die Primzahlen p mit low ≤ p ≤ high. Denk daran, dass 0 und 1 keine Primzahlen sind. Mit einem Sieb bis high lässt sich das schnell beantworten.
Implementiere count_primes_in_range(low, high).
Eingabe
low: Die untere Grenze, eingeschlossen.
high: Die obere Grenze, eingeschlossen.
Ausgabe
Gib die Anzahl der Primzahlen im Intervall zurück. Ist low > high, ist das Intervall leer und die Antwort 0.
Einschränkungen
0 ≤ low ≤ 1.000.000
0 ≤ high ≤ 1.000.000
Beispiele
Eingabe:
low = 1
high = 100
Erwartete Ausgabe:
expected = 25
Eingabe:
long long low = 1;
long long high = 100;
Erwartete Ausgabe:
long long expected = 25;
Eingabe:
long low = 1;
long high = 100;
Erwartete Ausgabe:
long expected = 25;
Erläuterung
Bis 100 gibt es 25 Primzahlen (2, 3, 5, … 97), also lautet die Antwort 25.
Eingabe:
low = 50
high = 60
Erwartete Ausgabe:
expected = 2
Eingabe:
long long low = 50;
long long high = 60;
Erwartete Ausgabe:
long long expected = 2;
Eingabe:
long low = 50;
long high = 60;
Erwartete Ausgabe:
long expected = 2;
Erläuterung
Zwischen 50 und 60 sind nur 53 und 59 prim, also lautet die Antwort 2.
So gehst du vor
Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.
Hinweis 1
Baue ein Sieb bis high und streiche die Vielfachen jeder Primzahl, beginnend bei ihrem Quadrat.
Hinweis 2
Zähle danach die Zahlen von low bis high, die noch als prim markiert sind.
Hinweis 3
Ist low größer als high, musst du gar nichts berechnen.
Erwartete Komplexität
Zeit O(high log log high), zusätzlicher Speicher O(high)
Referenzen
Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.