Programa de números perfectos en Python: ¿Cómo verificar si un número es perfecto o no?
Publicado: 2021-01-29Introducción
Se dice que un número es el número perfecto si la suma de sus divisores propios (sin incluir el número en sí) es igual al número.
Para tener una mejor idea, consideremos un ejemplo, los divisores propios de 6 son 1, 2, 3. Ahora la suma de estos divisores es igual a 6 (1+2+3=6), por lo que se dice que 6 es un número perfecto . Mientras que si consideramos otro número como el 12, los divisores propios de 12 son 1, 2, 3, 4, 6. Ahora bien, la suma de estos divisores no es igual a 12, por lo que 12 no es un número perfecto.
La programación en Python es relativamente más simple y divertida en comparación con otros lenguajes debido a su sintaxis más simple y buena legibilidad. Ahora que tenemos claro el concepto de número perfecto, escribamos un programa en Python para comprobar si un número es un número perfecto o no. Construyamos un código de python para verificar si la entrada del usuario dada es un número perfecto o no y exploremos la diversión de codificar con python. Eche un vistazo a nuestros programas de ciencia de datos si está interesado en adquirir experiencia.
Leer: Programas de patrones de Python
Tabla de contenido
Programa Python
Una solución básica para encontrar un número perfecto es pasar del 2 al número 1, mantener la suma de sus divisores propios y verificar si la suma es igual al número.
| n=int(entrada(“ingrese el número”)) suma=1 para i en el rango (2, n): si(n%i==0): suma=suma+i si(suma==n): print(n,”es un número perfecto”) demás: print(n,”no es un número perfecto”) |
Repasemos el código.
Primero inicializamos n con la entrada del usuario y lo encasillamos en un número entero porque, de forma predeterminada, la entrada del usuario se lee como una cadena en python. Tenemos que comprobar si n es un número perfecto o no. Tenga en cuenta que estamos inicializando la suma con 1 porque 1 es un divisor adecuado para todos los números enteros (excepto cero), por lo que podemos excluir una iteración en el ciclo y comenzar directamente desde 2.
Estamos haciendo un bucle sobre 2 al número 1 y sumando los enteros para sumar si es un divisor adecuado. Y por último, cuando salimos del bucle estamos comprobando si la suma obtenida es igual o no al número. Pan comido, ¿verdad?
Versión poco optimizada
Después de hacer un simulacro del programa anterior, es posible que tengamos una pregunta: ¿podemos optimizarlo? Bueno, pero podemos reducir el número de iteraciones a número/2 sin cambiar el algoritmo. Porque se nos ocurrió la idea de que un número no puede tener un divisor propio mayor que número/2.
| n=int(entrada(“ingrese el número”)) suma=1 para i en rango(2,n//2+1): si(n%i==0): suma=suma+i si(suma==n): print(n,”es un número perfecto”) demás: print(n, “no es un número perfecto”) |
El fragmento anterior es casi similar al anterior, con la única diferencia de que se repite hasta el número/2. Tenga en cuenta que estamos realizando una división de enteros para evitar convertirlo en un tipo flotante, y estamos recorriendo hasta n//2+1 porque el último entero en el rango no se considera en el ciclo de python.
Limitaciones
Cuando se nos pide que encontremos números perfectos en un rango dado, nuestra solución consumirá un tiempo proporcional al número ^ 2, es decir, O (n²) complejidad de tiempo. Porque necesitamos recorrer cada número en el rango dado y luego verificar los divisores adecuados para cada número. Y pocos números satisfacen la condición del número perfecto. Por ejemplo, la cantidad de números perfectos en el rango de 0 a 1000 es solo 3 (6, 28, 496).
Hay una solución optimizada para esto en la que no necesitamos recorrer todos los elementos para encontrar los divisores adecuados, la fórmula de Euclides establece que 2 n −1 (2 n − 1) es un número perfecto par donde tanto n, (2 n − 1) es números primos. Por ejemplo, 6 satisface la ecuación anterior con n como 2 y ambos 2, 2 2 − 1 (2 2 − 1 = 3) son números primos. Pero no podemos responder si se nos pide que averigüemos si hay números perfectos impares.
Además, sabemos que cada idioma tiene un límite en el rango de números enteros que puede almacenar. Con esta limitación, es posible que no tengamos una forma de encontrar el número perfecto más grande.
Todas estas limitaciones se enfrentan si nuestro número de entrada es grande, pero si nuestro número de entrada es pequeño, nuestra solución inicial funcionará en menos tiempo.
Lea también: Python Framework para desarrollo web
Conclusión
Conocemos la definición y entendimos el concepto detrás del número perfecto. Recorrido una solución básica para encontrar un número es un número perfecto o no. Y después de ver la solución inicial, la hemos optimizado un poco al reducir el número de iteraciones. Hemos superado las limitaciones de nuestro algoritmo y discutimos la fórmula de Euclides para encontrar el número par perfecto.
Ahora que conoce el programa python para verificar si un número es un número perfecto o no. Intente escribir el código por su cuenta e intente optimizarlo si encuentra iteraciones superpuestas. Además, intente construir el código para encontrar números perfectos en el rango de números dado.
Si tiene curiosidad por aprender sobre python, ciencia de datos, consulte el Programa PG ejecutivo en ciencia de datos de IIIT-B y upGrad, que se creó para profesionales que trabajan y ofrece más de 10 estudios de casos y proyectos, talleres prácticos prácticos, tutoría con expertos de la industria. , 1 a 1 con mentores de la industria, más de 400 horas de aprendizaje y asistencia laboral con las mejores empresas.
Explicar las complejidades del programa de números perfectos en Python.
Se dice que un número es número perfecto si es igual a la suma de sus divisores. Para comprobar si un número es perfecto o no, tenemos dos enfoques. El primer enfoque es un enfoque ingenuo donde la complejidad del tiempo es O(n2) ya que estamos iterando "j" veces para cada "i" y verificando sus divisores.
El segundo enfoque es la solución optimizada donde la complejidad del tiempo es O(√n). Aquí no necesitamos iterar sobre cada número. Podemos concluirlo directamente usando la fórmula de Euclides que es:
2n−1(2n − 1), donde n y 2n son números primos.
Sin embargo, esta fórmula no funciona para los números perfectos impares y, por lo tanto, tenemos que encontrar otro enfoque para ellos.
¿Cuáles son las limitaciones de los enfoques del Programa Número Perfecto?
Ambos enfoques son buenos, pero solo hasta cierto punto. Ninguno de ellos puede considerarse como el enfoque perfecto debido a algunos tecnicismos. Las limitaciones de estos enfoques son las siguientes:
1. El primer enfoque e ingenuo es peor porque consume mucho tiempo y memoria y tiene una complejidad de tiempo de O(n2). Esto se debe a que estamos usando un ciclo anidado e iterando el ciclo interno n veces para cada elemento del ciclo externo. Este enfoque es ingenuo y dará TLE para valores más grandes de n y, por lo tanto, no se recomienda.
2. Entonces tenemos un enfoque optimizado que resuelve el problema en O(√n). Este es un buen enfoque a menos que entren en juego los números perfectos impares. No podemos verificar los números perfectos impares con este enfoque, ya que se basa en la "fórmula de Euclides para números perfectos pares" que solo funciona para números perfectos pares.
¿Python es adecuado para la programación competitiva?
Python evolucionó de C/C++ e incluso de Java y se considera el lenguaje más adecuado para fines de investigación y desarrollo. Pero cuando se trata de programación competitiva, la mayoría de la comunidad de programación evita Python. La razón es que Python es el más lento entre estos tres lenguajes.