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

Suma de divisores propios

Suma todos los divisores de n que son menores que n.

Lo que aprenderás

  • Encontrar divisores por parejas
  • Detener el bucle en la raíz cuadrada
  • No contar dos veces un divisor que es raíz cuadrada

Problema

Ver original (inglés)

Los divisores propios de n son sus divisores positivos distintos del propio n. Para 12 son 1, 2, 3, 4 y 6. Su suma (a veces llamada suma alícuota) indica si un número es perfecto, abundante o deficiente. Los divisores van en parejas d y n / d, así que basta con probar valores de d hasta la raíz cuadrada de n.

Implementa sum_of_proper_divisors(n).

Entrada

n: un entero positivo.

Salida

Devuelve la suma de todos los divisores positivos de n que son menores que n. Para n = 1 no hay ninguno, así que devuelve 0.

Restricciones

1 ≤ n ≤ 10^12

Ejemplos

Ejemplo 1
Entrada:
n = 12

Salida esperada:
expected = 16
Entrada:
long long n = 12;

Salida esperada:
long long expected = 16;
Entrada:
long n = 12;

Salida esperada:
long expected = 16;

Explicación

1 + 2 + 3 + 4 + 6 = 16.

Ejemplo 2
Entrada:
n = 28

Salida esperada:
expected = 28
Entrada:
long long n = 28;

Salida esperada:
long long expected = 28;
Entrada:
long n = 28;

Salida esperada:
long expected = 28;

Explicación

1 + 2 + 4 + 7 + 14 = 28, así que 28 es un número perfecto.

Cómo abordarlo

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

Pista 1

Si d divide a n, entonces n / d también divide a n.

Pista 2

Prueba d solo hasta la raíz cuadrada de n y suma los dos miembros de cada pareja.

Pista 3

No incluyas el propio n, y suma la raíz cuadrada una sola vez cuando n sea un cuadrado perfecto.

Complejidad esperada

tiempo O(sqrt n), espacio extra O(1)

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.