Todos los desafíos
Difícil 0 resueltos 0% de aceptación

Sumas no abundantes

Suma los números hasta un límite que no se pueden escribir como suma de dos números abundantes.

Lo que aprenderás

  • Calcular con una criba las sumas de divisores de un intervalo
  • Marcar las sumas alcanzables con un arreglo booleano
  • Cortar un doble bucle en cuanto las sumas superan el límite

Problema

Ver original (inglés)

Un número es abundante cuando sus divisores propios (todos sus divisores excepto él mismo) suman más que él. El 12 es el menor: 1 + 2 + 3 + 4 + 6 = 16. Algunos números se pueden escribir como suma de dos números abundantes (se puede usar el mismo dos veces, como en 24 = 12 + 12) y otros no. Suma todos los enteros positivos del 1 a limit que no se pueden escribir así.

Implementa non_abundant_sums(limit).

Calcula de una vez las sumas de divisores de todos los números con una criba, haz la lista de los números abundantes y marca cada suma de dos de ellos que no supere el límite.

Entrada

limit: el mayor número que hay que comprobar.

Salida

Devuelve la suma de todos los n con 1 ≤ n ≤ limit que no son suma de dos números abundantes.

Restricciones

1 ≤ limit ≤ 10,000

Ejemplos

Ejemplo 1
Entrada:
limit = 23

Salida esperada:
expected = 276
Entrada:
long long limit = 23;

Salida esperada:
long long expected = 276;
Entrada:
long limit = 23;

Salida esperada:
long expected = 276;

Explicación

Ningún par de números abundantes suma 23 o menos, así que todos los números cuentan: 1 + 2 + ... + 23 = 276.

Ejemplo 2
Entrada:
limit = 30

Salida esperada:
expected = 411
Entrada:
long long limit = 30;

Salida esperada:
long long expected = 411;
Entrada:
long limit = 30;

Salida esperada:
long expected = 411;

Explicación

Quedan fuera 24 = 12 + 12 y 30 = 12 + 18, así que la respuesta es 465 − 24 − 30 = 411.

Cómo abordarlo

Inténtalo primero por tu cuenta y luego abre las pistas una a una.

Pista 1

Para cada i, suma i a la suma de divisores de 2i, 3i, 4i, ...

Pista 2

Reúne los números abundantes en orden creciente.

Pista 3

Para cada pareja a ≤ b, detén el bucle interior en cuanto a + b supere el límite.

Complejidad esperada

tiempo O(limit log limit + A²) para A números abundantes, espacio extra O(limit)

Referencias

Este reto está adaptado para CodeUtility. Sigue el enunciado y las restricciones indicadas arriba.

Clasificación

Clasificación completa

La mejor solución aprobada de cada programador. Las más rápidas, ligeras y mejor valoradas van primero.

Aún no hay soluciones aprobadas. Resuélvelo y quédate el primer puesto.

Aprende de otros

Soluciones de la comunidad

Aún no hay soluciones publicadas. Resuelve este reto para compartir la primera.