Steven D'Aprano <steve+comp.lang.pyt...@pearwood.info> writes:
> primes = sieve [2..]
> sieve (p : xs) = p : sieve [x | x <- xs, x `mod` p > 0]
> In her paper http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf, Melissa
> O'Neill calls this the "Sleight on Eratosthenes".
Oh cool, I wrote very similar Haskell code and converted it to Python.
I probably saw it before though, so it looks like a case of
not-exactly-independent re-invention.
> def turner():
> nums = itertools.count(2)
> while True:
> prime = next(nums)
> yield prime
> nums = filter(lambda v, p=prime: (v % p) != 0, nums)
This is nice, though it will still hit the nesting limit about equally
soon, because of the nested filters. I like the faster versions in the
O'Neill paper.
> On my computer, your recursive version is about 35% slower than the
> iterative version over the first 499 primes.
Interesting. I wonder why it's slower.
A Hamming (or "5-smooth") number is a number with no prime factors
larger than 5. So 20 (= 2*2*5) is a Hamming number but 21 (= 3*7) is
not. The first few of them are:
[1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24]
Here's an ugly computation of the millionth Hamming number, converted
from Haskell code that you've probably seen. I'd be interested in
seeing a cleaner implementation.
================================================================
import itertools, time
def merge(a0,b0):
def advance(m): m[0] = next(m[1])
a = [next(a0), a0]
b = [next(b0), b0]
while True:
if a[0] == b[0]:
yield a[0]
advance(a)
advance(b)
elif a[0] < b[0]:
yield a[0]
advance(a)
else:
yield b[0]
advance(b)
def hamming(n):
hh = [1]
def hmap(k):
for i in itertools.count():
yield k * hh[i]
m = merge(hmap(2),merge(hmap(3), hmap(5)))
for i in xrange(n):
hh.append(next(m))
return hh[-1]
# this takes about 2.4 seconds on my i5 laptop with python 2.7,
# about 2.8 sec with python 3.3.2
t0=time.time()
print (hamming(10**6-1))
print (time.time()-t0)
================================================================
--
https://mail.python.org/mailman/listinfo/python-list
