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