Tutte le sfide
Facile 0 risolte 0% di accettazione

Contare i numeri primi in un intervallo

Conta quanti numeri primi ci sono tra due estremi, entrambi inclusi.

Cosa imparerai

  • Segnare i numeri composti con un crivello
  • Contare i valori segnati dentro un intervallo
  • Gestire gli intervalli vuoti e i numeri 0 e 1

Problema

Quanti numeri primi ci sono da 1 a 100? E da 50 a 60? Conta i primi p con low ≤ p ≤ high. Ricorda che 0 e 1 non sono primi. Un crivello fino a high dà la risposta in poco tempo.

Implementa count_primes_in_range(low, high).

Input

low: l'estremo inferiore, incluso.

high: l'estremo superiore, incluso.

Output

Restituisci il numero di primi nell'intervallo. Se low > high l'intervallo è vuoto e la risposta è 0.

Vincoli

0 ≤ low ≤ 1 000 000

0 ≤ high ≤ 1 000 000

Esempi

Esempio 1
Input:
low = 1
high = 100

Output atteso:
expected = 25
Input:
long long low = 1;
long long high = 100;

Output atteso:
long long expected = 25;
Input:
long low = 1;
long high = 100;

Output atteso:
long expected = 25;

Spiegazione

Fino a 100 ci sono 25 primi (2, 3, 5, … 97), quindi la risposta è 25.

Esempio 2
Input:
low = 50
high = 60

Output atteso:
expected = 2
Input:
long long low = 50;
long long high = 60;

Output atteso:
long long expected = 2;
Input:
long low = 50;
long high = 60;

Output atteso:
long expected = 2;

Spiegazione

Tra 50 e 60 sono primi solo 53 e 59, quindi la risposta è 2.

Come affrontarlo

Prova prima da solo, poi apri un suggerimento alla volta.

Suggerimento 1

Costruisci un crivello fino a high, cancellando i multipli di ogni primo a partire dal suo quadrato.

Suggerimento 2

Poi conta i numeri ancora segnati come primi da low a high.

Suggerimento 3

Se low è maggiore di high, non c'è nulla da calcolare.

Complessità attesa

tempo O(high log log high), spazio aggiuntivo O(high)

Riferimenti

Questa sfida è adattata per CodeUtility. Segui la traccia e i vincoli sopra.

La migliore soluzione superata di ogni programmatore. Le più veloci, leggere e meglio valutate stanno in alto.

Ancora nessuna soluzione superata. Risolvila e prendi il primo posto.

Impara dagli altri

Soluzioni della community

Nessuna soluzione pubblicata. Risolvi questa sfida per condividere la prima.