Aprender Python
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.
Refs.:
Prolog
- https://prof.ti.bfh.ch/hew1/informatik3/prolog/p-99/
- https://sites.google.com/site/prologsite/prolog-problems
Haskell
lisp
Python
- http://davesquared.net/2008/03/99-problems-with-python-1-10.html
- http://wiki.python.org/moin/ProblemSets/99%20Prolog%20Problems%20Solutions
Criado/Created: NaN
Última actualização/Last updated: 10-10-2022 [14:26]
(c) Tiago Charters de Azevedo