[Edu-sig] Generating prime numbers
kirby urner
kirby.urner at gmail.com
Sun Apr 5 16:57:31 CEST 2009
Excellente! kind sir.
> I don't know about Python, but there are lazy evaluation languages
> with streams that can handle something like
>
> isprime=: {n.0 in [2:floor(sqrt(n))] | n}
>
> isprime each [2:_]/[2:_]
I'm wanting to say Haskell but that's just talking through my hat.
Once you get it down to a line, they'll complain it's not just one
symbol, which it sort of is in J, or at least converting to cyclic
notation is a primitive (my J __dict__ is a bit scrambled from lack of
much practice).
Under the hood though, you've got reams of chip flops, no matter how
crypto-poetic the mathematics. So I resist the trend to always
compress to the next level. Python feels less compressed than APL
too, but that's a feature not a bug.
On Sat, Apr 4, 2009 at 2:30 PM, Edward Cherlin <echerlin at gmail.com> wrote:
> Your message text got stuck in an attachment, where I almost missed
> it. I wonder what your mail system thinks it is doing? Comment below.
Kirby interpolating, cutting and pasting from Python 3:
>>> from itertools import count
>>> from math import sqrt
>>> def prime_gen():
"""
Generate all prime numbers
"""
primes = []
for n in count(2):
if all(n%p for p in primes if p <= sqrt(n)):
primes.append(n)
yield n
>>> p = prime_gen()
>>> next(p)
2
>>> next(p)
3
>>> next(p)
5
>>> next(p)
7
>>> next(p)
11
>>> next(p)
13
>>> next(p)
17
>>> next(p)
19
>
> On Sat, Apr 4, 2009 at 12:48 PM, John Posner <jjposner at snet.net> wrote:
>
>
> Sent today to python-list ...
>
> Inspired by recent threads (and recalling my first message to Python
> edu-sig), I did some Internet searching on producing prime numbers using
> Python generators. Most algorithms I found don't go for the infinite,
> contenting themselves with "list all the primes below a given number".
>
> Here's a very Pythonic (IMHO) implementation that keeps going and going and
> going ...:
>
> from itertools import count
> from math import sqrt
>
> def prime_gen():
> """
> Generate all prime numbers
> """
> primes = []
> for n in count(2):
> if all(n%p for p in primes if p <= sqrt(n)):
> primes.append(n)
> yield n
>
> The use of all() is particularly nifty (see
> http://code.activestate.com/recipes/576640/). And so is the way in which the
> list comprehension easily incorporates the sqrt(n) optimization.
>
> Question: Is there a way to implement this algorithm using generator
> expressions only -- no "yield" statements allowed?
>
> I don't know about Python, but there are lazy evaluation languages
> with streams that can handle something like
>
> isprime=: {n.0 in [2:floor(sqrt(n))] | n}
>
> isprime each [2:_]/[2:_]
>
> where
>
> floor is round down
> | is remainder (mod)
> each applies a function to each member of the argument
> _ is positive infinity
> / (compress) returns elements of the right argument corresponding to
> True values in the left argument
>
> and we can get rid of the named function by simple substitution, thus
>
> {n.0 in [2:floor(sqrt(n))] | n} [2:_]
>
> 2 passes as prime because [2:1] is empty, so it generates no 0 remainder.
>
> Can you say that in Python?
> --
> Silent Thunder (默雷/धर्ममेघशब्दगर्ज/دھرممیگھشبدگر ج) is my name
> And Children are my nation.
> The Cosmos is my dwelling place, The Truth my destination.
> http://earthtreasury.net/ (Edward Mokurai Cherlin)
> _______________________________________________
> Edu-sig mailing list
> Edu-sig at python.org
> http://mail.python.org/mailman/listinfo/edu-sig
>
More information about the Edu-sig
mailing list