Aprender Python

Código em python para factorização de números inteiros

Tenho andado a aprender a programar em Python e por isso comecei a fazer os 99 problemas 1. Esta lista é baseada na original em PROLOG.

Python é mais imperativa do que funcional, mas mesmo assim vale a pena.

O problema 35 é de um dos mais estimulantes:

Determine the prime factors of a given positive integer.

A maneira mais simples, e a primeira que fiz, usa o crivo de Eratóstenes

# 35. Determine the prime factors of a given positive integer.
#     Construct a flat list containing the prime factors in ascending order.

import math

def isprime (n):
    q=map(lambda x: float(n)/x,[2]+range(3,math.trunc(math.sqrt(n))+1,2))
    if n<2:
        return False
    elif n==2:
        return True
    else:
        aux=map((lambda x,y:not x==y),q,map(lambda x: math.trunc(x),q))
        return map((lambda x:True),aux)==aux

def isprime_n (n):
    if isprime(n): return n

def genprimes (n):
    p=range(2,n+1)
    p=map(lambda x: isprime_n(x), p)
    return rm_none(p)

def rm_none (lst):
    aux=lst
    retval=[]
    i=0
    for x in aux:
        if not x==None:
            retval.append(x)
            i=i+1
    return retval

def primefactor (n):
    "This works for small n."
    p=genprimes(n)
    pf=[]
    if isprime(n):
        pf.append(n)
        return pf
    else:
        for pi in p:
            while  n % pi == 0:
                pf.append(pi)
                n=n/pi
            if isprime(n):
                pf.append(n)
                return pf
            elif n==1:
                return pf

Por exemplo:

>>> primefactor(3016)
[2, 2, 2, 13, 29]

Não é de facto a mais elegante mas resolve o problema para valores pequenos de n.

Claro que o problema está quando se quer calcular a factorização de 4434353535435160. Para este "tipo" de números o algoritmo rho de Pollard resolve o problema.

>>> list(factor(4434353535435160))
[2, 2, 2, 5L, 5261L, 21881L, 963019L]

def gcd (a,b):
    while not b==0:
        t = b
        b = a % b
        a = t
    return a

def pollard(n,c):
    if n % 2 == 0: return 2
    def f(z,c,n):
        return (pow(z,2)+c) % n
    x,y,d=2,2,1
    while d==1:
        x=f(x,c,n)
        y=f(f(y,c,n),c,n)
        d=gcd(abs(x-y),n)
    return d

def factor(n):
    m=2
    lmax=n**0.5
    while m<=lmax:
        m=pollard(n,1)
        if n % m == 0:
            yield m
            n=n/m
            lmax=n**0.5
    if n > 1:
        yield n

Para o F5 (número de Fermat) o resultado é quase instantâneo:

>>> list(factor(4294967297))
[641L, 6700417L]
para factorizar o F6 é preciso mais tempo 
>>> list(factor(18446744073709551617))
[274177L, 67280421310721L]

A ideia era factorizar este 13256278887989457651018865901401704640L num tempo relativamente curto! Mas nem mesmo este algoritmo o faz!

Gosto de muito de métodos de Monte Carlo e o algoritmo rho de Pollard pode ser visto como um. Para breve mais notas sobre Pollard. E claro uma versão em LISP do mesmo.

1.

Refs.:

Prolog

Haskell

lisp

Python

Palavras chave/keywords: python, primos, factorização,Pollard

Criado/Created: NaN

Última actualização/Last updated: 10-10-2022 [14:26]

Voltar à página inicial.

GNU/Emacs Creative Commons License

(c) Tiago Charters de Azevedo