find all multiplicands and multipliers for a number

Rustom Mody rustompmody at gmail.com
Thu Apr 16 06:17:51 CEST 2015


On Wednesday, April 15, 2015 at 8:07:31 AM UTC+5:30, Paul Rubin wrote:
> Steven D'Aprano 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)

Here's a massive parallel (and more massively inefficient)
Turner sieve as bash script

$ cat nos2

n=2
while true ; do
	echo $n
	n=$(($n + 1))
done

$ cat filt 
read x
while true ; do
    if [ $(($x % $1))  -ne 0 ] ; then
	echo $x
    fi
    read x
done


$ cat sieve
read x
echo $x
filt $x | sieve


Call as
nos2|sieve|less
For 1st ten primes

$ nos2|sieve |head
2
3
5
7
11
13
17
19
23
29



More information about the Python-list mailing list