Problema
Un numero è abbondante quando la somma dei suoi divisori propri (tutti i divisori tranne il numero stesso) supera il numero. Il più piccolo è 12: 1 + 2 + 3 + 4 + 6 = 16. Alcuni numeri si possono scrivere come somma di due numeri abbondanti (anche usando due volte lo stesso, come 24 = 12 + 12), altri no. Somma tutti gli interi positivi da 1 a limit che non si possono scrivere così.
Implementa non_abundant_sums(limit).
Calcola le somme dei divisori di tutti i numeri in una volta con un crivello, elenca i numeri abbondanti e poi segna ogni somma di due di essi che resta entro il limite.
Input
limit: il numero più grande da controllare.
Output
Restituisci la somma di tutti gli n con 1 ≤ n ≤ limit che non sono somma di due numeri abbondanti.
Vincoli
1 ≤ limit ≤ 10 000
Esempi
Input:
limit = 23
Output atteso:
expected = 276
Input:
long long limit = 23;
Output atteso:
long long expected = 276;
Input:
long limit = 23;
Output atteso:
long expected = 276;
Spiegazione
Nessuna coppia di numeri abbondanti ha somma 23 o meno, quindi contano tutti i numeri: 1 + 2 + ... + 23 = 276.
Input:
limit = 30
Output atteso:
expected = 411
Input:
long long limit = 30;
Output atteso:
long long expected = 411;
Input:
long limit = 30;
Output atteso:
long expected = 411;
Spiegazione
24 = 12 + 12 e 30 = 12 + 18 restano esclusi, quindi la risposta è 465 − 24 − 30 = 411.
Come affrontarlo
Prova prima da solo, poi apri un suggerimento alla volta.
Suggerimento 1
Per ogni i, aggiungi i alla somma dei divisori di 2i, 3i, 4i, ...
Suggerimento 2
Raccogli i numeri abbondanti in ordine crescente.
Suggerimento 3
Per ogni coppia a ≤ b, interrompi il ciclo interno appena a + b supera il limite.
Complessità attesa
tempo O(limit log limit + A²) per A numeri abbondanti, spazio aggiuntivo O(limit)
Riferimenti
Questa sfida è adattata per CodeUtility. Segui la traccia e i vincoli sopra.