Alle Herausforderungen
Einfach 0 gelöst 0% Erfolgsquote

Primzahlen in einem Intervall zählen

Zähle, wie viele Primzahlen zwischen zwei Grenzen liegen, beide Grenzen eingeschlossen.

Das lernst du

  • Zusammengesetzte Zahlen mit einem Sieb markieren
  • Markierte Werte innerhalb eines Intervalls zählen
  • Leere Intervalle und die Zahlen 0 und 1 behandeln

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

Beispiel 1
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.

Beispiel 2
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.

Die beste bestandene Lösung jedes Coders. Schnellere, sparsamere und besser bewertete Lösungen stehen weiter oben.

Noch keine bestandene Lösung. Löse sie und hol dir Platz eins.

Von anderen lernen

Community-Lösungen

Noch keine veröffentlichten Lösungen. Löse die Aufgabe und teile als Erster eine Lösung.