Alle Herausforderungen
Einfach 0 gelöst 0% Erfolgsquote

Count Primes in a Range

Count how many prime numbers lie between two bounds, both included.

Das lernst du

  • Mark composite numbers with a sieve
  • Count marked values inside a range
  • Handle empty ranges and the numbers 0 and 1

Problem

Übersetzung anzeigen

How many primes are there from 1 to 100? From 50 to 60? Count the primes p with low ≤ p ≤ high. Remember that 0 and 1 are not prime. A sieve up to high answers this quickly.

Implement count_primes_in_range(low, high).

Input

low: The lower bound, included.

high: The upper bound, included.

Output

Return the number of primes in the range. If low > high the range is empty and the answer is 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

There are 25 primes up to 100 (2, 3, 5, … 97), so the answer is 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

Only 53 and 59 are prime between 50 and 60, so the answer is 2.

So gehst du vor

Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.

Hinweis 1

Build a sieve up to high, crossing out multiples of each prime starting at its square.

Hinweis 2

Then count the numbers still marked prime from low to high.

Hinweis 3

If low is greater than high, nothing needs to be computed.

Erwartete Komplexität

O(high log log high) time, O(high) extra space

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.