Perfect Number
Un divisor propio de n es un divisor positivo menor que n. Un número perfecto es igual a la suma de sus divisores propios: 6 = 1 + 2 + 3. Recibes un entero positivo n. Devuelve true si n es perfecto y false en caso contrario.
Función
- ninteger
- el entero positivo que se va a comprobar
- Devuelveboolean
- verdadero si n es igual a la suma de sus divisores propios, falso en caso contrario
Restricciones
1 ≤ n ≤ 108
Ejemplos
- Entrada
- n = 28
- Salida
- true
- Explicación
- Los divisores propios de
28son1,2,4,7y14. Suman28, así que28es perfecto.
- Entrada
- n = 12
- Salida
- false
- Explicación
- Los divisores propios de
12son1,2,3,4y6. Suman16, que supera12.
- Entrada
- n = 1
- Salida
- false
- Explicación
1no tiene ningún divisor propio, así que la suma es0, no1.
+16 pruebas ocultas al enviar
Para ir más allá
Todo número perfecto par tiene la forma 2^(p-1) × (2^p-1), donde 2^p-1 es primo. ¿Puedes enumerar todos los números perfectos menores que 10^8 usando esa fórmula, sin probar cada número?
Pistas
Ábrelas de una en una. Cada una revela un poco más.
Escribe los divisores propios de
28. ¿Cuáles encontrarías si solo buscaras entre los números hasta5?Los divisores vienen en pares: si
ddivide an, también lo hacen / d. Un miembro de cada par es como máximo√n.Inicia el total en
1, devuelvefalseparan == 1y recorreddesde2mientrasd * d ≤ n. Sumadyn / d, pero solo una vez cuando sean iguales.
Solución
La definición pide una suma de divisores, y el bucle obvio prueba todos los candidatos hasta n / 2. Para n = 10^8, eso supone 5 × 10^7 divisiones. Los divisores vienen en pares cuyo producto es n, así que puedes recopilar ambos miembros de cada par mientras buscas solo hasta √n, unos 10^4 pasos.
Añade cada divisor propio
Correcto, pero no termina con las pruebas más grandes
Intuición
Sigue la definición. Prueba cada d desde 1 hacia arriba y, cuando n % d == 0, suma d a un total acumulado. Al final, compara el total con n. Para 28, el bucle recoge 1, 2, 4, 7 y 14, y 1 + 2 + 4 + 7 + 14 = 28.
Puedes detenerte en n / 2. Un divisor distinto de n deja un cociente de al menos 2, así que nunca es más de la mitad de n. El límite también sirve para n = 1: el bucle se ejecuta cero veces, el total permanece en 0 y la respuesta es false.
Reducir el rango a la mitad no cambia el crecimiento. Para n = 10^8, el bucle todavía se ejecuta 5 × 10^7 veces, y lo hace para cada entrada de ese tamaño, sea o no divisor.
Algoritmo
- Establece
totalen0. - Recorre
ddesde1hastan / 2. - Si
n % d == 0, sumadatotal. - Devuelve si
total == n.
def isPerfect(n):
total = 0
# No proper divisor of n is larger than n / 2.
for d in range(1, n // 2 + 1):
if n % d == 0:
total += d
return total == nRecopila pares de divisores hasta la raíz cuadrada
Intuición
Cuando d divide a n, también lo hace n / d. Para 28, los pares son 1 × 28, 2 × 14 y 4 × 7. En cada par, uno de los miembros es como máximo √n, porque dos números mayores que √n multiplicados dan más que n. Así que una búsqueda hasta √n encuentra cada par una vez, y vas sumando ambos miembros a medida que avanzas.
Hay que tener cuidado con dos miembros. El par 1 × n incluye al propio n, que no es un divisor propio: empieza el total en 1 y la búsqueda en 2. Ese inicio es incorrecto para n = 1, cuyo único divisor es él mismo, así que primero devuelve false en ese caso. Y cuando n es un cuadrado, la raíz forma un par consigo misma: para 36, 6 × 6 debe sumar 6 una vez, no dos.
Escribe el límite como d * d ≤ n, lo que mantiene los números enteros. Para n = 10^8, el bucle se detiene en d = 10^4, así que se ejecuta unas 10^4 veces en lugar de 5 × 10^7.
Algoritmo
- Si
n == 1, devuelvefalse. - Establece
totalen1yden2. - Mientras
d * d ≤ n: siddivide an, sumady suma tambiénn / dcuando sea distinto ded. - Pasa al siguiente
d. - Devuelve si
total == n.
def isPerfect(n):
if n == 1:
return False
total = 1 # 1 divides every n > 1; n itself does not count
d = 2
while d * d <= n:
if n % d == 0:
total += d
partner = n // d
if partner != d: # a square root pairs with itself: add it once
total += partner
d += 1
return total == n
Errores comunes y casos límite
El truco de los pares es breve, y cada uno de sus errores cambia la suma exactamente en un divisor.
- Contar el propio
n. El par1 × nsuman, y después todos los números parecen tener una suma superior an. Empieza el total en1y la búsqueda en2. - Considerar que
1es perfecto. Con el total iniciado en1, la entrada1se compara con1 == 1. La suma de sus divisores propios es0, así que manéjalo antes del bucle. - Sumar dos veces una raíz cuadrada. Para
16, los divisores propios son1,2,4y8, que suman15. Sumar4dos veces da19. - Detenerse en
d * d < n. Eso omite por completo la raíz cuadrada, así que nunca se cuenta el4de16. - Tomar el límite de una raíz cuadrada de punto flotante. En precisión simple, o por encima de
2^53en precisión doble, la raíz de un cuadrado perfecto puede resultar una unidad menor y omitir un divisor. La pruebad * d ≤ nse mantiene en números enteros y nunca tiene ese problema.
Preguntas frecuentes4
¿Cuál es la complejidad temporal de comprobar si un número es perfecto?
Recopilar pares de divisores hasta √n toma un tiempo O(√n) y un espacio O(1). Para n = 10^8, eso equivale a unos 10^4 pasos. Probar cada candidato hasta n / 2 es O(n), unos 5 × 10^7 pasos para la misma entrada.
¿Cuántos números perfectos hay por debajo de 10^8?
Cinco: 6, 28, 496, 8128 y 33550336. Se vuelven escasos rápidamente. El siguiente, 8589869056, ni siquiera cabe en un entero de 32 bits.
¿Existen números perfectos impares?
Nadie lo sabe. Todos los números perfectos encontrados hasta ahora son pares. Las búsquedas han descartado números perfectos impares menores que 10^1500, pero ninguna demostración afirma que no puedan existir. Tu función debe basarse en la definición, no en suponer que la entrada es par.
¿Cuál es la diferencia entre los números perfectos, abundantes y deficientes?
Compara la suma de los divisores propios con el número. Si son iguales, es perfecto, como 28. Si la suma es mayor, es abundante, como 12, cuyos divisores suman 16. Si es menor, es deficiente, como todo número primo, cuyo único divisor propio es 1.
Problemas similares
Problemas que usan las mismas ideas. Resolver dos o tres es lo que fija un patrón.
Python
def isPerfect(n):
# Escribe el código aquíCaso 1
Caso 2
Caso 3
Entrada
n = 28
Esperado
true