Todos os desafios
Difícil 0 resolvidos 0% de aceitação

Somas não abundantes

Some os números até um limite que não podem ser escritos como a soma de dois números abundantes.

O que você vai aprender

  • Calcular somas de divisores de um intervalo com um crivo
  • Marcar as somas alcançáveis em um array booleano
  • Interromper um laço duplo quando as somas passam do limite

Problema

Ver original (inglês)

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

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

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

A melhor solução aprovada de cada programador. As mais rápidas, leves e mais bem avaliadas ficam no topo.

Ainda não há soluções aprovadas. Resolva e fique com o primeiro lugar.

Aprenda com outros

Soluções da comunidade

Ainda não há soluções publicadas. Resolva este desafio para compartilhar a primeira.