# find all multiplicands and multipliers for a number

Steven D'Aprano steve+comp.lang.python at pearwood.info
Tue Apr 14 15:40:46 CEST 2015

```On Tue, 14 Apr 2015 12:42 pm, Paul Rubin wrote:

> Steven D'Aprano <steve+comp.lang.python at pearwood.info> writes:
>> http://code.activestate.com/recipes/577821-integer-square-root-function/
>
> The methods there are more "mathematical" but probably slower than what
> I posted.
>
> Just for laughs, this prints the first 20 primes using Python 3's
> "yield from":
>
>     import itertools
>
>     def sieve(ps):
>         p = ps.__next__()
>         yield p
>         yield from sieve(a for a in ps if a % p != 0)
>
>     primes = sieve(itertools.count(2))
>     print(list(itertools.islice(primes,20)))
>
> It's not that practical above a few hundred primes, probably.

Oh! I thought that looked familiar... that's a recursive version of David
Turner's implementation of Euler's sieve. It is very popular in Haskell
circles, usually written as:

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".

According to O'Neill, it has asymptotic performance of O(N**2/(log N)**2),
which means that it will perform very poorly beyond a few hundred primes.

Here is an iterative version:

def turner():
nums = itertools.count(2)
while True:
prime = next(nums)
yield prime
nums = filter(lambda v, p=prime: (v % p) != 0, nums)

On my computer, your recursive version is about 35% slower than the
iterative version over the first 499 primes.

--
Steven

```