Problema
Um número é abundante quando a soma dos seus divisores próprios (todos os divisores, exceto ele mesmo) é maior que ele. O menor é 12: 1 + 2 + 3 + 4 + 6 = 16. Alguns números podem ser escritos como a soma de dois números abundantes (o mesmo pode ser usado duas vezes, como em 24 = 12 + 12) e outros não. Some todos os inteiros positivos de 1 a limit que não podem.
Implemente non_abundant_sums(limit).
Calcule a soma dos divisores de todos os números de uma vez com um crivo, liste os números abundantes e depois marque toda soma de pares que fique dentro do limite.
Entrada
limit: o maior número a verificar.
Saída
Retorne a soma de todos os n com 1 ≤ n ≤ limit que não são a soma de dois números abundantes.
Restrições
1 ≤ limit ≤ 10 000
Exemplos
Entrada:
limit = 23
Saída esperada:
expected = 276
Entrada:
long long limit = 23;
Saída esperada:
long long expected = 276;
Entrada:
long limit = 23;
Saída esperada:
long expected = 276;
Explicação
Nenhum par de números abundantes soma 23 ou menos, então todos os números contam: 1 + 2 + ... + 23 = 276.
Entrada:
limit = 30
Saída esperada:
expected = 411
Entrada:
long long limit = 30;
Saída esperada:
long long expected = 411;
Entrada:
long limit = 30;
Saída esperada:
long expected = 411;
Explicação
24 = 12 + 12 e 30 = 12 + 18 ficam de fora, então a resposta é 465 − 24 − 30 = 411.
Como abordar
Tente sozinho primeiro e depois abra uma dica de cada vez.
Dica 1
Para cada i, some i à soma dos divisores de 2i, 3i, 4i, ...
Dica 2
Reúna os números abundantes em ordem crescente.
Dica 3
Para cada par a ≤ b, interrompa o laço interno assim que a + b passar do limite.
Complexidade esperada
tempo O(limit log limit + A²) para A números abundantes, espaço extra O(limit)
Referências
Este desafio foi adaptado para o CodeUtility. Siga o enunciado e as restrições acima.