from math import sqrt

def fatoracao_fermat(n):
    """Encontra fatores de um número usando o algoritmo de Fermat, ou conclui que ele é primo"""
    if n%2 == 0:
        return 2, n//2
    
    x = int(sqrt(n))

    if x**2 == n:
        return x

    y = 0.1
    
    while(y != int(y) and x <= (n+1)//2):
        x += 1
        y = sqrt(x**2 - n)
        print(str.format("x = {:d}, y = {:6.2f}, x-y = {:7.2f}, x+y = {:7.2f}",x,y,x-y,x+y))

    if x >= (n+1)//2:
        return str(n) + " é primo"

    return int(x-y), int(x+y)

def menor_fator(n):
    """Retorna o menor fator k de n tal que 1 < k"""
    k = 2
    
    while n%k != 0 and k <= sqrt(n):
        k += 1
        
    if k > sqrt(n):
        return n
    
    return k

def fatoracao_ingenua(n):
    """Retorna a lista completa dos fatores primos de n"""
    fatores = {}
    N = n
    
    while N != 1:
        k = menor_fator(N)

        if k not in fatores:
            fatores[k] = 1
        else:
            fatores[k] += 1
            
        N //= k

    return fatores