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

Os fatores primos de 13195 são 5, 7, 13 e 29. Qual o maior primo fator de 600851475143? Existe uma solução mais interessante que essa você possivelmente apresentou?

0 votos
545 visitas
perguntada Mar 19, 2016 em Programação Computacional por danielcajueiro (5,661 pontos)  
Compartilhe

2 Respostas

+1 voto
respondida Mar 19, 2016 por danielcajueiro (5,661 pontos)  

Uma solução muito simples em Python é

if __name__ == '__main__':
    n=600851475143
    i=2
    while i*i <= n:
        if(n%i==0):
            n=n/i
        else:
            i=i+1
    print n

É válido mencionar que essa não é normalmente a primeira solução que as pessoas pensam.

+1 voto
respondida Abr 12, 2016 por Carlos O. (6 pontos)  
editado Abr 12, 2016 por Carlos O.

Implementei uma solução diferente, que pega o último loop da minha solução para um problema anterior, de fatoração (o código para fatoração que implementei reproduz o procedimento para fatoração que ensinam pra gente bem cedo na escola):

def largest_factor(n):
    if n <= 0:
        if n < 0:
            return largest_factor(-n)
        else:
            return '0 has no integer factors.'
    elif n == 1:
        return [1]
    else: # the following is a version of xisk's step-by-step suggested algorithm (posted to StackExchange thread http://math.stackexchange.com/questions/389675/largest-prime-factor-of-600851475143 , which was last checked on April 10, 2016), adapted according to the suggestion made by user Arulx Z in response to xisk
        a = n
        b = 2
        c = 0
        while a >= c:
            if a % b == 0:
                c = b
                a = a/c
            else:
                b = b+1
        return c

if __name__ = '__main__' 
    n = int(raw_input('Input the integer "n" whose largest prime factor you want to find: '))
    print 'The largest prime factor of %s is %s' % (n,largest_factor(n))
...