On 22/06/2011 06:58, Chris Torek wrote:
Now that the exercise has been solved...
Instead of "really short code to solve the problem", how about
some "really long code"? :-)
I was curious about implementing prime factorization as a generator,
using a prime-number generator to come up with the factors, and
doing memoization of the generated primes to produce a program that
does what "factor" does, e.g.:
$ factor 99999999999999999
99999999999999999: 3 3 2071723 5363222357
The python code is rather too slow for this particular number (I
gave up on it finding 5363222357) but works quite well on 600851475143,
or even, e.g., 12186606004219:
$ python factor.py 600851475143 12186606004219
600851475143: 71 839 1471 6857
12186606004219: 2071723 5882353
[snip]
This code isn't particularly efficient, but it's fast enough:
import math
n = 99999999999999999
limit = math.sqrt(n)
test = 2
factors = []
while test <= limit:
if n % test == 0:
factors.append(test)
n //= test
limit = math.sqrt(n)
else:
test += 1
factors.append(n)
print(factors)
--
http://mail.python.org/mailman/listinfo/python-list
