Problema
Un numero primo è un intero maggiore di 1 divisibile solo per 1 e per sé stesso. Somma tutti i numeri primi strettamente minori di limit. Il valore di limit stesso è escluso anche se è primo.
Implementa prime_sum(limit).
Input
limit: Il limite superiore esclusivo.
Output
Restituisci la somma dei numeri primi ammessi, oppure 0 se non ne esistono.
Vincoli
0 ≤ limit ≤ 2.000.000. Restituisci la somma utilizzando un intero con segno a 64 bit.
Esempi
Input:
limit = 12
Output atteso:
expected = 28Input:
long long limit = 12;
Output atteso:
long long expected = 28;Input:
long limit = 12;
Output atteso:
long expected = 28;Spiegazione
I numeri primi inferiori a 12 sono 2, 3, 5, 7 e 11; la loro somma è 28.
Input:
limit = 2
Output atteso:
expected = 0Input:
long long limit = 2;
Output atteso:
long long expected = 0;Input:
long limit = 2;
Output atteso:
long expected = 0;Spiegazione
Non ci sono numeri primi strettamente inferiori a 2.
Come affrontarlo
Prova prima da solo, poi apri un suggerimento alla volta.
Suggerimento 1
Il costo principale è trovare i primi in modo efficiente; controlli di divisibilità naïf per ogni numero sarebbero troppo lenti.
Suggerimento 2
Usa un approccio tipo crivello per segnare i composti, poi somma i numeri rimasti non segnati e sotto il limite.
Suggerimento 3
Ricorda che il limite stesso è escluso, anche se è primo, e per limiti piccoli il contributo può essere nullo.
Complessità attesa
tempo O(limit log log limit), spazio aggiuntivo O(limit)
Riferimenti
Questa sfida è adattata per CodeUtility. Segui la traccia e i vincoli sopra.