Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

Como posso testar um intervalo possui números perfeitos?

+3 votos
532 visitas
perguntada Mai 6, 2016 em Ciência da Computação por Saulo (451 pontos)  

Faça um programa para testar se um número no intervalor \( \{1, \ldots, N \} \) é um número perfeito e quando for guarde esse número em um vetor. Um número perfeito é um número que é igual a soma dos seus divisores menores que ele. Por exemplo, \( 6=1+2+3 \) ou \( 28=1+2+4+7+14 \). Qual a complexidade desse algoritmo?

Compartilhe

2 Respostas

+4 votos
respondida Mai 6, 2016 por Saulo (451 pontos)  

Código-fonte:

def obter_divisores(n):
    lista_divisores = list()
    for i in range(1, n+1):
        if (n % i == 0):
            lista_divisores.append(i)
    return lista_divisores

def eh_numero_perfeito(n):
    divisores = obter_divisores(n)
    soma_divisor = 0
    for divisor in divisores:
        if (divisor < n):
            soma_divisor += divisor
    return (soma_divisor == n)

def obter_numeros_perfeitos(N):
    lista_numeros_perfeitos = list()
    for k in range(1, N+1):
        if (eh_numero_perfeito(k)):
            lista_numeros_perfeitos.append(k)
    return lista_numeros_perfeitos

if __name__ == '__main__':

    N = 30
    print obter_numeros_perfeitos(N)

Complexidade:
\( \sum_{i=1}^{N}{ \sum_{j=1}^{i}{c} } = c\sum_{i=1}^{N}{ i } = c(N+1)N/2 \in O(N^2) \)

Algum erro? Favor me avisar. Dúvidas e sugestões são sempre bem-vindos!

+1 voto
respondida Mai 10, 2017 por Caue (231 pontos)  

Outra Solução:

def perfeito(n_max):
    lista = []
    for n in range(1, n_max + 1):
        soma = 0
        for div in range(1, n):
            if n % div == 0:
                soma += div
        if n == soma:
            lista.append(n)
    return lista


print(perfeito(9000))
...