Tutte le sfide
Difficile 0 risolte 0% di accettazione

Somme non abbondanti

Somma i numeri fino a un limite che non si possono scrivere come somma di due numeri abbondanti.

Cosa imparerai

  • Calcolare con un crivello le somme dei divisori di un intervallo
  • Segnare le somme raggiungibili in un array di booleani
  • Interrompere un doppio ciclo appena le somme superano il limite

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

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

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

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.