Programa de números perfeitos em Python: como verificar se um número é perfeito ou não?
Publicados: 2021-01-29Introdução
Diz-se que um número é perfeito se a soma de seus divisores próprios (sem incluir o próprio número) for igual ao número.
Para ter uma ideia melhor vamos considerar um exemplo, divisores próprios de 6 são 1, 2, 3. Agora a soma desses divisores é igual a 6 (1+2+3=6), então 6 é um número perfeito . Considerando que se considerarmos outro número como 12, divisores próprios de 12 são 1, 2, 3, 4, 6. Agora a soma desses divisores não é igual a 12, então 12 não é um número perfeito.
Programar em Python é relativamente mais simples e divertido quando comparado a outras linguagens por causa de sua sintaxe mais simples, boa legibilidade. Agora que entendemos o conceito de número perfeito, vamos escrever um programa em Python para verificar se um número é um número perfeito ou não. Vamos construir um código python para verificar se a entrada do usuário fornecida é um número perfeito ou não e explorar a diversão na codificação com python. Dê uma olhada em nossos programas de ciência de dados se você estiver interessado em obter experiência.
Leia: Programas de padrão Python
Índice
Programa Python
Uma solução básica para encontrar um número perfeito é fazer um loop de 2 para número-1, manter a soma de seus divisores próprios e verificar se a soma é igual ao número.
| n=int(input(“digite o número”)) soma=1 para i no intervalo(2,n): if(n%i==0): soma=soma+i if(soma==n): print(n,"é um número perfeito") outro: print(n,"não é um número perfeito") |
Vamos percorrer o código.
Estamos primeiro inicializando n com a entrada do usuário e convertendo-o em um inteiro porque, por padrão, a entrada do usuário é lida como uma string em python. Precisamos verificar se n é um número perfeito ou não. Observe que estamos inicializando a soma com 1 porque 1 é um divisor adequado para todos os inteiros (excluindo zero), de modo que podemos excluir uma iteração no loop e começar diretamente de 2.
Estamos fazendo um loop de 2 para o número-1 e adicionando os inteiros à soma se for um divisor adequado. E finalmente, quando saímos do loop estamos verificando se a soma obtida é igual ao número ou não. Pedaço de bolo certo?
Versão pouco otimizada
Depois de fazer uma simulação do programa acima, podemos ter uma pergunta: podemos otimizá-lo? Bem, mas podemos reduzir o número de iterações para number/2 sem alterar o algoritmo. Porque tivemos a ideia de que um número não pode ter um divisor próprio maior que número/2.
| n=int(input(“digite o número”)) soma=1 para i no intervalo(2,n//2+1): if(n%i==0): soma=soma+i if(soma==n): print(n,"é um número perfeito") outro: print(n, “não é um número perfeito”) |
O trecho acima é quase semelhante ao anterior, com a única diferença de fazer um loop até number/2. Observe que estamos realizando uma divisão inteira para evitar convertê-la em um tipo float, e estamos fazendo um loop até n//2+1 porque o último inteiro no intervalo não é considerado no loop python.
Limitações
Quando somos solicitados a encontrar números perfeitos em um determinado intervalo, nossa solução consumiria tempo proporcional a number^2, ou seja, O(n²) complexidade de tempo. Porque precisamos percorrer cada número no intervalo fornecido e, em seguida, verificar os divisores adequados para cada número. E poucos números satisfazem a condição de número perfeito. Por exemplo, o número de números perfeitos no intervalo de 0 a 1000 é apenas 3 (6, 28, 496).
Existe uma solução otimizada para isso onde não precisamos fazer um loop sobre todos os elementos para encontrar divisores adequados, a fórmula de Euclides afirma que 2 n −1(2 n − 1) é um número perfeito par onde tanto n, (2 n − 1) é números primos. Por exemplo, 6 satisfaz a equação acima com n como 2 e ambos 2, 2 2 − 1 (2 2 − 1 = 3) são números primos. Mas não podemos responder se nos pedirem para descobrir se existem números perfeitos ímpares.
Além disso, sabemos que toda linguagem tem um limite para o intervalo de inteiros que pode armazenar. Com essa limitação, talvez não tenhamos como encontrar o maior número perfeito.
Todas essas limitações são enfrentadas se nosso número de entrada for grande, mas se nosso número de entrada for pequeno, nossa solução inicial funcionaria em menos tempo.
Leia também: Estrutura Python para Desenvolvimento Web
Conclusão
Conhecemos a definição e entendemos o conceito por trás do número perfeito. Andou por uma solução básica para encontrar um número é um número perfeito ou não. E depois de observar a solução inicial, nós a otimizamos um pouco reduzindo o número de iterações. Superamos as limitações do nosso algoritmo e discutimos a fórmula de Euclides para encontrar o número perfeito par.
Agora que você está ciente do programa python para verificar se um número é um número perfeito ou não. Tente escrever o código por conta própria e tente otimizá-lo se encontrar iterações sobrepostas. Além disso, tente construir o código para encontrar números perfeitos em um determinado intervalo de números.
Se você está curioso para aprender sobre python, ciência de dados, confira o Programa PG Executivo em Ciência de Dados do IIIT-B & upGrad, criado para profissionais que trabalham e oferece mais de 10 estudos de caso e projetos, workshops práticos práticos, orientação com especialistas do setor , 1-on-1 com mentores do setor, mais de 400 horas de aprendizado e assistência de trabalho com as principais empresas.
Explique as complexidades do programa Perfect Number em Python.
Um número é dito perfeito se for igual à soma de seus divisores. Para verificar se um número é perfeito ou não, temos duas abordagens. A primeira abordagem é uma abordagem ingênua onde a complexidade de tempo é O(n2), pois estamos iterando “j” vezes para cada “i” e verificando seus divisores.
A segunda abordagem é a solução otimizada onde a complexidade de tempo é O(√n). Aqui não precisamos iterar sobre cada número. Podemos concluir diretamente usando a fórmula de Euclides que é:
2n−1(2n − 1), onde n e 2n são números primos.
No entanto, esta fórmula não funciona para os números perfeitos ímpares e, portanto, temos que encontrar outra abordagem para eles.
Quais são as limitações das abordagens do Programa Número Perfeito?
Ambas as abordagens são boas, mas apenas até certo ponto. Nenhum deles pode ser considerado como a abordagem perfeita devido a alguns aspectos técnicos. As limitações dessas abordagens são as seguintes:
1. A primeira e ingênua abordagem é pior porque consome muito tempo e memória e tem uma complexidade de tempo O(n2). Isso ocorre porque estamos usando um loop aninhado e iterando o loop interno n vezes para cada elemento do loop externo. Essa abordagem é ingênua e fornecerá TLE para valores maiores de n e, portanto, não é recomendada.
2. Então temos uma abordagem otimizada que resolve o problema em O(√n). Esta é uma boa abordagem, a menos que os números perfeitos ímpares entrem em jogo. Não podemos verificar os números perfeitos ímpares com esta abordagem, pois é baseada na “fórmula de Euclides para números perfeitos pares” que só funciona para números perfeitos pares.
O Python é adequado para programação competitiva?
Python evoluiu de C/C++ e até mesmo Java e é considerada a linguagem mais adequada para fins de pesquisa e desenvolvimento. Mas quando se trata de programação competitiva, a maioria da comunidade de programação evita o Python. A razão é que o Python é o mais lento entre essas três linguagens.