Re: Prime number generator

[Ian Kelly]

On Tue, Jul 30, 2013 at 4:58 AM, Albert van der Horst
 wrote:
> Notice that all values from i on are possibly present.
> So you are better off with a list indexed by forthcoming i's and
> each item containing a list of primes. What you do then, more or less,
> is keep track of all dividers of primes to be.
> This promises to be reasonable efficient.
> I've done a similar thing in Forth.

What do you do when you get up into the billions?  It seems
inefficient to keep a mostly empty billion-element list hanging
around.

> There is an unpleasant fact about this kind of generators.
> If you want to go unbounded, you've no choice but remember all
> primes. If you go bounded, you need to remember 168 up til 1M,
> say sqrt(limit)/log(limit). This dramatic difference (and the lack
> of processors) leads one quickly to decide for some upper bound.

Actually, take a look at the generator that I posted in this thread,
which avoids this.  It is unbounded but gets away with only
remembering sqrt(N) primes by recursively regenerating the primes
already seen as needed.  Thus it only uses (2 * N**(1/2) + 4 *
N**(1/4) 8 * N**(1/8) + ...) / log(N) extra memory, which I believe is
O(sqrt(N)).
-- 
http://mail.python.org/mailman/listinfo/python-list

Re: Prime number generator

[bryanjugglercryptographer]

Chris Angelico wrote:
> Bas wrote:
> > Still trying to figure out your algorithm ...
> 
> It's pretty simple. (That's a bad start, I know!) Like the Sieve of
> Eratosthenes, it locates prime numbers, then deems every multiple of
> them to be composite. Unlike the classic sieve, it does the "deem"
> part in parallel. Instead of marking all the multiples of 2 first,
> then picking three and marking all the multiples of 3, then 5, etc,
> this function records the fact that it's up to (say) 42 in marking
> multiples of 2, and then when it comes to check if 43 is prime or not,
> it moves to the next multiple of 2. This requires memory to store the
> previously-known primes, similarly to other methods, but needs no
> multiplication or division.

Knuth points to the method, using a priority queue, in exercise 15 of section 
5.2.3 of /Sorting and Searching/, and credits it to "B. A. Chartres".

-- 
-Bryan
-- 
http://mail.python.org/mailman/listinfo/python-list

Re: Prime number generator

[Albert van der Horst]

In article ,
Chris Angelico   wrote:
>And now for something completely different.
>
>I knocked together a prime number generator, just for the fun of it,
>that works like a Sieve of Eratosthenes but unbounded. It keeps track
>of all known primes and the "next composite" that it will produce -
>for instance, after yielding 13, the prime map will be {2: 20, 3: 18,
>5: 20, 7: 21, 11: 22, 13: 26}, each one mapped to the first multiple
>greater than 13.
>
>Notable in the algorithm is an entire lack of division, or even
>multiplication. Everything is done with addition.
>
>So, a few questions. Firstly, is there a stdlib way to find the key
>with the lowest corresponding value? In the above map, it would return
>3, because 18 is the lowest value in the list. I want to do this with
>a single pass over the dictionary. Secondly, can the "while
>iit, but not quite there. Thirdly, is there any sort of half-sane
>benchmark that I can compare this code to? And finally, whose wheel
>did I reinvent here? What name would this algorithm have?

Notice that all values from i on are possibly present.
So you are better off with a list indexed by forthcoming i's and
each item containing a list of primes. What you do then, more or less,
is keep track of all dividers of primes to be.
This promises to be reasonable efficient.
I've done a similar thing in Forth.

I've also done a slightly different but related parallel program on a
multi-processor Forth machine where each processor takes care of one
prime.

There is an unpleasant fact about this kind of generators.
If you want to go unbounded, you've no choice but remember all
primes. If you go bounded, you need to remember 168 up til 1M,
say sqrt(limit)/log(limit). This dramatic difference (and the lack
of processors) leads one quickly to decide for some upper bound.

>
>Code tested on Python 3.3, would probably run fine on pretty much any
>Python that supports yield, though I don't have a Py2.2 to test from
>__future__ import generators on!

I had problems with the print statement on a 2 version, fixed easy
enough.

>
>ChrisA
>
># -- start --
>def primes():
>   """Generate an infinite series of prime numbers."""
>   i=2
>   yield 2
>   prime={2:2} # Map a prime number to its next composite (but bootstrap 
> with 2:2)
>   while True:
>   # Find the smallest value in prime[] and its key.
>   # Is there a standard library way to do this??
>   # (If two values are equal smallest, either can be returned.)
>   prm=None
>   for p,val in prime.items():
>   if prm is None or val   prm,smallest=p,val
>   prime[prm]+=prm
>   while i   yield i
>   prime[i]=i+i
>   i+=1
>   if i==smallest: i+=1
>
>gen=primes()
>for i in range(30):
>   print(next(gen),end="\t") # Star Trek?
>print()
># -- end --
-- 
Albert van der Horst, UTRECHT,THE NETHERLANDS
Economic growth -- being exponential -- ultimately falters.
albert@spe&ar&c.xs4all.nl &=n http://home.hccnet.nl/a.w.m.van.der.horst

-- 
http://mail.python.org/mailman/listinfo/python-list

Re: Prime number generator

[Joshua Landau]

On 10 July 2013 19:56, Ian Kelly  wrote:
> On Wed, Jul 10, 2013 at 11:47 AM, Joshua Landau  wrote:
 If you care about speed, you might want to check the heapq module. 
 Removing the smallest item and inserting a new item in a heap both cost 
 O(log(N)) time, while finding the minimum in a dictionary requires 
 iterating over the whole dictionary, which cost O(N) time.
>>
>> Actually, because it's a list under the hood I'd imagine push and pop
>> still take O(n) time :/.
>
> It shouldn't.  You can implement push by appending the new item and
> then getting it into the right place by performing O(log n) swaps.
> Likewise for pop, you can update the heap with O(log n) swaps and then
> removing the tail element.  Appending or removing the tail element of
> a list is amortized O(1).

Genius. Bas replied off-list that it won't matter too much anyway as
they're over-allocated, but this makes tons of sense.

>> PS: It's faster to use heapreplace(...) than
>> heappop(...);heappush(...) but it only saves a few %.
>
> The problem with heapreplace here is that the value to be pushed
> is dependent on the value returned by pop.

That's fine because indexing is much faster than pop. The "few %" was
a real statistic from working, timed code.
-- 
http://mail.python.org/mailman/listinfo/python-list

Re: Prime number generator

[Ian Kelly]

On Wed, Jul 10, 2013 at 11:47 AM, Joshua Landau  wrote:
>>> If you care about speed, you might want to check the heapq module. Removing 
>>> the smallest item and inserting a new item in a heap both cost O(log(N)) 
>>> time, while finding the minimum in a dictionary requires iterating over the 
>>> whole dictionary, which cost O(N) time.
>
> Actually, because it's a list under the hood I'd imagine push and pop
> still take O(n) time :/.

It shouldn't.  You can implement push by appending the new item and
then getting it into the right place by performing O(log n) swaps.
Likewise for pop, you can update the heap with O(log n) swaps and then
removing the tail element.  Appending or removing the tail element of
a list is amortized O(1).

> PS: It's faster to use heapreplace(...) than
> heappop(...);heappush(...) but it only saves a few %.

The problem with heapreplace here is that the value to be pushed
is dependent on the value returned by pop.
-- 
http://mail.python.org/mailman/listinfo/python-list

Re: Prime number generator

[Joshua Landau]

On 10 July 2013 17:15, Chris Angelico  wrote:
> On Thu, Jul 11, 2013 at 1:47 AM, bas  wrote:
>> On Wednesday, July 10, 2013 5:12:19 PM UTC+2, Chris Angelico wrote:
>>> Well, that does answer the question. Unfortunately the use of lambda
>>> there has a severe performance cost [ ...]
>> If you care about speed, you might want to check the heapq module. Removing 
>> the smallest item and inserting a new item in a heap both cost O(log(N)) 
>> time, while finding the minimum in a dictionary requires iterating over the 
>> whole dictionary, which cost O(N) time.

Actually, because it's a list under the hood I'd imagine push and pop
still take O(n) time :/.

> Ehh, speed isn't the ultimate. I was just trying to avoid something
> that worked out ridiculously slow (a Python function call IS quite
> slow). I haven't profiled the code to find out where the bulk of the
> time is spent, but switching in the lambda-based version doubled total
> run time, so I didn't like it :)
>
>> (untested)
>> #before loop
>> from heapq import *
>> primes = [(2,2)] #heap of tuples (multiple, prime). start with 1 item, so no 
>> need for heapify
>>
>> #during loop
>> smallest, prm = heappop(primes)
>> heappush(primes, (smallest+prm, prm))
>>
>> #when new prime found
>> heappush(primes, (i+i, i))
>
> Ahh, that's the bit I should have thought of! Of course.
>
> My original thought experiment had involved basically a really long
> list, like the classic Sieve but getting longer as time moves on, with
> composites replaced by None and primes with their next-markers, which
> I then collapsed to a dict. Always I was thinking in terms of indexing
> with the prime to get its next composite. Here's the code involving
> heapq:
>
> # -- start --
> def primes():
> """Generate an infinite series of prime numbers."""
> from heapq import heappush,heappop
> i=2
> yield 2
> prime=[(2,2)] # Heap
> while True:
> smallest, prm = heappop(prime)
> heappush(prime, (smallest+prm, prm))
> while i     yield i
> heappush(prime, (i+i, i))
> i+=1
> if i==smallest: i+=1
>
> gen=primes()
> print([next(gen) for i in range(10)])
> for i in range(1000):
> next(gen) # Star Trek?
> print("The next prime number is:",next(gen))
> # -- end --
>
> And that's significantly shorter, clearer, AND faster than the original. 
> Thanks!

AFAICT, that's exactly my code but using a less-efficient storage
medium and a *much* more efficient sorting mechanism. It'd be
interesting what could happen if heapq didn't reject blists -- they
have better efficiency for changing list sizes (which this code does a
lot of).

Thanks for the heads-up on heapq, by the way -- it's new to me and a
blimmin' good idea.

PS: It's faster to use heapreplace(...) than
heappop(...);heappush(...) but it only saves a few %.
-- 
http://mail.python.org/mailman/listinfo/python-list

Re: Prime number generator

[Chris Angelico]

On Thu, Jul 11, 2013 at 2:54 AM, Ian Kelly  wrote:
> As promised.  Apologies for the excessive commenting.  As noted, this
> implementation is a recursive generator, which is done so that the
> primes in the sieve can go only up to the square root of the current
> prime, rather than tossing in every prime seen so far.
>


Nice. Comes in at 0.23369310904039478 in my oh-so-scientific
benchmarking, so it's comparable to several of Steven's algorithms.
Runs on Python 3.3 with just the tiny tweak of converting iter.next()
to next(iter).

ChrisA
-- 
http://mail.python.org/mailman/listinfo/python-list

Re: Prime number generator

[Ian Kelly]

On Wed, Jul 10, 2013 at 10:16 AM, Ian Kelly  wrote:
> The other interesting thing about my sieve is that it's a recursive
> generator.  I'll dig it up later and share it.

As promised.  Apologies for the excessive commenting.  As noted, this
implementation is a recursive generator, which is done so that the
primes in the sieve can go only up to the square root of the current
prime, rather than tossing in every prime seen so far.

from collections import defaultdict
from itertools import count, islice

def primes():
yield 2
# Set up the data structures.  multiples implements the sieve as a dict
# that marks upcoming composite numbers and records the prime factors
# that disqualified them.
multiples = defaultdict(list)
# subgen is a recursive sub-generator that supplies prime factors to be fed
# into the sieve.  islice is used to skip 2 (since we only consider odd
# numbers) and 3 (since we can't get it from subgen before we've yielded it
# below).
subgen = islice(primes(), 2, None)
# Initialize the sieve with the first prime factor q.
q = 3
# When we reach threshold (the square of the last prime added to the sieve),
# it's time to add another prime to the sieve.  By construction, threshold
# is always an odd composite.
threshold = q * q
multiples[threshold].append(q + q)
# The main loop tries every odd integer, starting with 3.
for p in count(3, 2):
if p in multiples:
# p is composite.  Discard the entry from multiples and mark the
# next odd multiple of each prime factor that disqualified p.
# Because the multiples dict actually stores the doubles of the
# prime factors, they need only be added once to get to the next
# odd multiple.
for q in multiples[p]:
multiples[p + q].append(q)
del multiples[p]
if p == threshold:
# All primes up to the previous q ** 2 have been generated.
# Get the next prime factor q and add it to the sieve.
q = subgen.next()
threshold = q * q
multiples[threshold].append(q + q)
else:
# p is prime.  Yay!
yield p
-- 
http://mail.python.org/mailman/listinfo/python-list

Re: Prime number generator

[Chris Angelico]

On Thu, Jul 11, 2013 at 2:01 AM, Steven D'Aprano
 wrote:
> On Thu, 11 Jul 2013 00:00:59 +1000, Chris Angelico wrote:
>> Thirdly, is there any sort of half-sane benchmark that I
>> can compare this code to? And finally, whose wheel did I reinvent here?
>> What name would this algorithm have?
>
> I can't directly answer that question, but I can make a shameless plug
> for this:
>
> https://pypi.python.org/pypi/pyprimes
>
> If your prime generator performs better than, or worse than, all of those
> in the above module, I may have to steal it from you :-)

Ha, that's what I was hoping for. My algorithm outperforms several of
yours! Look!

Rosuav: 0.10868923284942639
awful_primes: 16.55546780386893
naive_primes1: 2.6105180965737276
naive_primes2: 1.358270674066116
trial_division: 0.06926075800136644
turner: 0.5736550315752424
croft: 0.007141969160883832
sieve: 0.01786707528470899
cookbook: 0.014790147909859996
wheel: 0.015050236831779529

Okay, so I outperform only algorithms listed as toys... :| Here's
similar figures, going to a higher cutoff (I kept it low for the sake
of awful_primes) and using only the algos designed for real use:

Rosuav: 2.1318494389650082
croft: 0.11628042111497416
sieve: 0.26868582459502566
cookbook: 0.21551174800149164
wheel: 0.4761577239565362

I didn't seriously think that this would outperform mathematically
proven and efficient algorithms, it was just a toy. But at least now I
know: It's roughly 20 times slower than a leading algo. And that's
after the bas-suggested improvement of using a heap.

But hey. If you want the code, you're welcome to it - same with anyone
else. Here's the heap version as used in the above timings. MIT
license.

def primes():
"""Generate an infinite series of prime numbers."""
from heapq import heappush,heappop
i=2
yield 2
prime=[(2,2)] # Heap
while True:
smallest, prm = heappop(prime)
heappush(prime, (smallest+prm, prm))
if ihttp://mail.python.org/mailman/listinfo/python-list

Re: Prime number generator

[Chris Angelico]

On Thu, Jul 11, 2013 at 1:47 AM, bas  wrote:
> On Wednesday, July 10, 2013 5:12:19 PM UTC+2, Chris Angelico wrote:
>> Well, that does answer the question. Unfortunately the use of lambda
>> there has a severe performance cost [ ...]
> If you care about speed, you might want to check the heapq module. Removing 
> the smallest item and inserting a new item in a heap both cost O(log(N)) 
> time, while finding the minimum in a dictionary requires iterating over the 
> whole dictionary, which cost O(N) time.

Ehh, speed isn't the ultimate. I was just trying to avoid something
that worked out ridiculously slow (a Python function call IS quite
slow). I haven't profiled the code to find out where the bulk of the
time is spent, but switching in the lambda-based version doubled total
run time, so I didn't like it :)

> (untested)
> #before loop
> from heapq import *
> primes = [(2,2)] #heap of tuples (multiple, prime). start with 1 item, so no 
> need for heapify
>
> #during loop
> smallest, prm = heappop(primes)
> heappush(primes, (smallest+prm, prm))
>
> #when new prime found
> heappush(primes, (i+i, i))

Ahh, that's the bit I should have thought of! Of course.

My original thought experiment had involved basically a really long
list, like the classic Sieve but getting longer as time moves on, with
composites replaced by None and primes with their next-markers, which
I then collapsed to a dict. Always I was thinking in terms of indexing
with the prime to get its next composite. Here's the code involving
heapq:

# -- start --
def primes():
"""Generate an infinite series of prime numbers."""
from heapq import heappush,heappop
i=2
yield 2
prime=[(2,2)] # Heap
while True:
smallest, prm = heappop(prime)
heappush(prime, (smallest+prm, prm))
while i> > Still trying to figure out your algorithm ...
>> It's pretty simple.  [...]
> I understand what you are trying, but it is not immediately clear to me that 
> it works correctly if for example a smallest factor appears twice in the 
> list. I don't have time for it now, but it for sure can be simplified. The 
> while loop, for example, can be replaced by an if, since it will never 
> execute more than once (since if i is prime > 2, i+1 will be divisible by 2)

Ah, good point. Again, I originally was starting from 1, so the while
loop was necessary to catch 2 and 3 in the first run. When I changed
it to start at 2 and explicitly yield it first, I didn't notice to
change that.

It works correctly with the smallest multiple appearing twice because
it won't yield primes until the smallest value is higher than the
current next-prime. So when it's just yielded 11, for instance, both
the 2 and 3 slots hold 12; advancing one of those does nothing,
advancing the other allows the bottom loop to notice that 13 is now
lower than the minimum value (which will then be 14).

ChrisA
-- 
http://mail.python.org/mailman/listinfo/python-list

Re: Prime number generator

[Ian Kelly]

On Wed, Jul 10, 2013 at 8:00 AM, Chris Angelico  wrote:
> And now for something completely different.
>
> I knocked together a prime number generator, just for the fun of it,
> that works like a Sieve of Eratosthenes but unbounded. It keeps track
> of all known primes and the "next composite" that it will produce -
> for instance, after yielding 13, the prime map will be {2: 20, 3: 18,
> 5: 20, 7: 21, 11: 22, 13: 26}, each one mapped to the first multiple
> greater than 13.

Cool! I have a similar generator, and instead of mapping primes to
next composites, it maps next composites to lists of primes.  It works
using increment-by-2 and checking the dictionary rather than searching
for the min of the dictionary.  You could though adapt that data
structure and just use min(prime) to find the next composite (although
as somebody else noted, a heap would probably be more efficient).

The other interesting thing about my sieve is that it's a recursive
generator.  I'll dig it up later and share it.
-- 
http://mail.python.org/mailman/listinfo/python-list

Re: Prime number generator

[Steven D'Aprano]

On Thu, 11 Jul 2013 00:00:59 +1000, Chris Angelico wrote:

> And now for something completely different.
> 
> I knocked together a prime number generator, just for the fun of it,
> that works like a Sieve of Eratosthenes but unbounded.
[...]
> So, a few questions. Firstly, is there a stdlib way to find the key with
> the lowest corresponding value? In the above map, it would return 3,
> because 18 is the lowest value in the list. 

Not from a dict, but with a list you would probably use the bisect module.


> I want to do this with a
> single pass over the dictionary. Secondly, can the "while i i+=1" loop become a for...range? It's almost asking for it, but not
> quite there. Thirdly, is there any sort of half-sane benchmark that I
> can compare this code to? And finally, whose wheel did I reinvent here?
> What name would this algorithm have?

I can't directly answer that question, but I can make a shameless plug 
for this:

https://pypi.python.org/pypi/pyprimes

If your prime generator performs better than, or worse than, all of those 
in the above module, I may have to steal it from you :-)



-- 
Steven
-- 
http://mail.python.org/mailman/listinfo/python-list

Re: Prime number generator

[Chris Angelico]

On Thu, Jul 11, 2013 at 1:43 AM, Joshua Landau  wrote:
>> So, a few questions. Firstly, is there...
> Of course there is.
>
>> Secondly, can the...
> Of course it can.
>
>> Thirdly, is there...
> Of course there is. I have no clue what, though.

Heh, I guess I was asking for that kind of response :)

> The trick
> is to avoid that repeated effort of finding the minimum in the dict by
> just keeping a sorted list.
>
> I've mocked that up just now:
>
> # Faster code #
> from blist import sortedlist

Hmm, blist isn't part of the standard library, so I'd have to hunt
that down. Presumably it's on PyPI.

>> What name would this algorithm have?
> I'll call it "the flamingo".

Guess that's as good a name as any!

> def generate_primes():
> """Generate an infinite series of prime numbers."""
> i = 2
> yield 2
>
> primes = {2:2} # Map a prime number to its next composite (but
> bootstrap with 2:2)
> while True:
> prm = min(primes, key=primes.__getitem__)
> smallest = primes[prm]
>
> primes[prm] += prm
>
> for prm in range(i, smallest):
> yield prm
> primes[i] = 2*i
>
> i = smallest + 1
>
> gen=generate_primes()
> for i in range(30):
> print(next(gen),end="\t") # Star Trek?
> print()

And once again, a version that's slower than the original. This one
does at least have the advantage of readability, though, and it's only
a little slower, so I'd say this is the current winner. I would still
replace 2*i with i+i for the sake of boasting "no multiplication",
though :)

In terms of the "one pass" criterion I put on the find-smallest
algorithm, I had been seeking to avoid anything that involved constant
lookups into primes[]. But this solution does look very clean and
simple. I think.

ChrisA
-- 
http://mail.python.org/mailman/listinfo/python-list

Re: Prime number generator

[bas]

On Wednesday, July 10, 2013 5:12:19 PM UTC+2, Chris Angelico wrote:
> Well, that does answer the question. Unfortunately the use of lambda
> there has a severe performance cost [ ...]
If you care about speed, you might want to check the heapq module. Removing the 
smallest item and inserting a new item in a heap both cost O(log(N)) time, 
while finding the minimum in a dictionary requires iterating over the whole 
dictionary, which cost O(N) time.

(untested)
#before loop
from heapq import *
primes = [(2,2)] #heap of tuples (multiple, prime). start with 1 item, so no 
need for heapify

#during loop
smallest, prm = heappop(primes)
heappush(primes, (smallest+prm, prm))

#when new prime found
heappush(primes, (i+i, i))

> > Still trying to figure out your algorithm ...
> It's pretty simple.  [...]
I understand what you are trying, but it is not immediately clear to me that it 
works correctly if for example a smallest factor appears twice in the list. I 
don't have time for it now, but it for sure can be simplified. The while loop, 
for example, can be replaced by an if, since it will never execute more than 
once (since if i is prime > 2, i+1 will be divisible by 2)


-- 
http://mail.python.org/mailman/listinfo/python-list

Re: Prime number generator

[Joshua Landau]

On 10 July 2013 15:00, Chris Angelico  wrote:
> And now for something completely different.
>
> I knocked together a prime number generator, just for the fun of it,
> that works like a Sieve of Eratosthenes but unbounded. It keeps track
> of all known primes and the "next composite" that it will produce -
> for instance, after yielding 13, the prime map will be {2: 20, 3: 18,
> 5: 20, 7: 21, 11: 22, 13: 26}, each one mapped to the first multiple
> greater than 13.
>
> Notable in the algorithm is an entire lack of division, or even
> multiplication. Everything is done with addition.
>
> So, a few questions. Firstly, is there a stdlib way to find the key
> with the lowest corresponding value?

Of course there is.

> In the above map, it would return
> 3, because 18 is the lowest value in the list. I want to do this with
> a single pass over the dictionary. Secondly, can the "while
> i It's almost asking for
> it, but not quite there. Thirdly, is there any sort of half-sane
> benchmark that I can compare this code to?

Of course there is. I have no clue what, though.

> And finally, whose wheel
> did I reinvent here?

Mine :P. That just proves the algorithm is older still, though. You
also did it much more neatly and much more slowly, though. The trick
is to avoid that repeated effort of finding the minimum in the dict by
just keeping a sorted list.

I've mocked that up just now:

# Faster code #
from blist import sortedlist

def generate_primes():
primes = sortedlist()
primes.add([4, 2])

yield 2
i = 3

while True:
next_nonprime, prime_factor = primes.pop(0)

for prime in range(i, next_nonprime):
yield prime
primes.add([prime*2, prime])

i = next_nonprime + 1

primes.add([next_nonprime + prime_factor, prime_factor])
# No longer code #

> What name would this algorithm have?

I'll call it "the flamingo".

> Code tested on Python 3.3, would probably run fine on pretty much any
> Python that supports yield, though I don't have a Py2.2 to test from
> __future__ import generators on!
>
> ChrisA
>
> # -- start --
def generate_primes():
"""Generate an infinite series of prime numbers."""
i = 2
yield 2

primes = {2:2} # Map a prime number to its next composite (but
bootstrap with 2:2)
while True:
prm = min(primes, key=primes.__getitem__)
smallest = primes[prm]

primes[prm] += prm

for prm in range(i, smallest):
yield prm
primes[i] = 2*i

i = smallest + 1

gen=generate_primes()
for i in range(30):
print(next(gen),end="\t") # Star Trek?
print()
> # -- end --
-- 
http://mail.python.org/mailman/listinfo/python-list

Re: Prime number generator

[Chris Angelico]

On Thu, Jul 11, 2013 at 12:35 AM, Bas  wrote:
> On Wednesday, July 10, 2013 4:00:59 PM UTC+2, Chris Angelico wrote:
> [...]
>> So, a few questions. Firstly, is there a stdlib way to find the key
>> with the lowest corresponding value? In the above map, it would return
>> 3, because 18 is the lowest value in the list. I want to do this with
>> a single pass over the dictionary.
>
> In [1]: prime = {2: 20, 3: 18, 5: 20, 7: 21, 11: 22, 13: 26}
>
> In [2]: smallest_key = min(prime.iteritems(), key=lambda k_v: k_v[1])[0]
>
> In [3]: smallest_key
> Out[3]: 3

Well, that does answer the question. Unfortunately the use of lambda
there has a severe performance cost (roughly doubles the total run
time, when I ask for the thousandth prime), without majorly improving
readability. I'll bear it in mind if there's a way to make that work
on either readability or performance, but otherwise, I'll stick with
the explicit loop. Thanks anyway!

> Still trying to figure out your algorithm ...

It's pretty simple. (That's a bad start, I know!) Like the Sieve of
Eratosthenes, it locates prime numbers, then deems every multiple of
them to be composite. Unlike the classic sieve, it does the "deem"
part in parallel. Instead of marking all the multiples of 2 first,
then picking three and marking all the multiples of 3, then 5, etc,
this function records the fact that it's up to (say) 42 in marking
multiples of 2, and then when it comes to check if 43 is prime or not,
it moves to the next multiple of 2. This requires memory to store the
previously-known primes, similarly to other methods, but needs no
multiplication or division.

ChrisA
-- 
http://mail.python.org/mailman/listinfo/python-list

Re: Prime number generator

[Bas]

On Wednesday, July 10, 2013 4:00:59 PM UTC+2, Chris Angelico wrote:
[...]
> So, a few questions. Firstly, is there a stdlib way to find the key
> with the lowest corresponding value? In the above map, it would return
> 3, because 18 is the lowest value in the list. I want to do this with
> a single pass over the dictionary. 

In [1]: prime = {2: 20, 3: 18, 5: 20, 7: 21, 11: 22, 13: 26}

In [2]: smallest_key = min(prime.iteritems(), key=lambda k_v: k_v[1])[0]

In [3]: smallest_key
Out[3]: 3

Still trying to figure out your algorithm ...
-- 
http://mail.python.org/mailman/listinfo/python-list

Prime number generator

[Chris Angelico]

And now for something completely different.

I knocked together a prime number generator, just for the fun of it,
that works like a Sieve of Eratosthenes but unbounded. It keeps track
of all known primes and the "next composite" that it will produce -
for instance, after yielding 13, the prime map will be {2: 20, 3: 18,
5: 20, 7: 21, 11: 22, 13: 26}, each one mapped to the first multiple
greater than 13.

Notable in the algorithm is an entire lack of division, or even
multiplication. Everything is done with addition.

So, a few questions. Firstly, is there a stdlib way to find the key
with the lowest corresponding value? In the above map, it would return
3, because 18 is the lowest value in the list. I want to do this with
a single pass over the dictionary. Secondly, can the "while
ihttp://mail.python.org/mailman/listinfo/python-list

Re: Infinite prime number generator

[Thomas Mlynarczyk]

Thomas Jollans schrieb:

def primes():
yield 1


1 is not a prime number.

Greetings,
Thomas

--
Ce n'est pas parce qu'ils sont nombreux à avoir tort qu'ils ont raison!
(Coluche)
--
http://mail.python.org/mailman/listinfo/python-list

Re: Infinite prime number generator

[John Posner]

On 6/29/2010 12:51 PM, Thomas Jollans wrote:


def rprimes():
 def elim_mult(n):
 yield n
 for p in filter((lambda x:x%n != 0), elim_mult(n+1)): yield p
 yield 1
 for p in elim_mult(2): yield p



Thomas, take a look at the thread "Generators/iterators, Pythonicity, 
and primes" in the April 2009 archives of python-list. For example:


  from itertools import ifilter, count
  pgen = ifilter(
lambda n, primes=[]:
all(n%p for p in primes) and not primes.append(n),
count(2)
 )
  for _ in range(50): print pgen.next()

-John
--
http://mail.python.org/mailman/listinfo/python-list

Infinite prime number generator

[Thomas Jollans]

I've been toying with Haskell a bit, and after implementing
(essentially) the Sieve of Eratosthenes as an infinite list, thus:

primes = 1 : foldr elim_mult [] [2..]
where elim_mult n l = n : filter ((/=0) . (`mod` n)) l

I wondered how easy it would be to do the same thing in Python.
Obviously, Python doesn't have Haskell's infinite lists as such, and
normally evaluates expressions eagerly instead of lazily, but it's
still, with generators, relatively simple do create infinite sequences
(which aren't, strictly speaking, sequences)

So, here's the same thing as a Python generator, in a simple imperative
style:

def primes():
yield 1
i = 2
old = set()
while True:
for p in old:
if (i % p) == 0:
break
else:
old.add(i)
yield i
i += 1

Haskell:
*Main> take 10 primes
[1,2,3,5,7,11,13,17,19,23]
*Main>

Python:
>>> from itertools import islice
>>> list(islice(primes(), 0, 10))
[1, 2, 3, 5, 7, 11, 13, 17, 19, 23]
>>>

So far, so good. But then I thought, how close to the haskell version
can a Python generator get?
foldr is like functools.reduce, except that it's right-associative. In
Haskell, it works for infinite lists because Haskell is a lazy bastard,
but it's not that difficult to express the exactly same thing with
recursive generators:

if isinstance(filter(None, []), list): # Python 2
from itertools import ifilter as filter

def rprimes():
def elim_mult(n):
yield n
for p in filter((lambda x:x%n != 0), elim_mult(n+1)): yield p
yield 1
for p in elim_mult(2): yield p

This sort of works:
>>> list(islice(rprimes(), 0, 10))
[1, 2, 3, 5, 7, 11, 13, 17, 19, 23]
>>>

But it has a bit of a problem:
>>> sl = islice(rprimes(), None, None, 150) #step=150
>>> next(sl)
1
>>> next(sl)
863
>>> next(sl)

 [..]

  File "primes.py", line 21, in elim_mult
for p in filter((lambda x:x%n != 0), elim_mult(n+1)): yield p
  File "primes.py", line 21, in elim_mult
for p in filter((lambda x:x%n != 0), elim_mult(n+1)): yield p
  File "primes.py", line 21, in elim_mult
for p in filter((lambda x:x%n != 0), elim_mult(n+1)): yield p
RuntimeError: maximum recursion depth exceeded
>>>

If you happen to have a copy of stackless lying around, I'd expect it to
work!

-- Thomas
-- 
http://mail.python.org/mailman/listinfo/python-list

Re: Program to compute and print 1000th prime number

[Wayne Brehaut]

On Sat, 7 Nov 2009 19:34:47 +0100, Andre Engels
 wrote:

>On Sat, Nov 7, 2009 at 6:40 PM, Mensanator  wrote:
>
>>> Tongue in cheek solution:
>>>
>>> import urllib2
>>>
>>> url = 'http://primes.utm.edu/lists/small/1.txt'
>>> primes = []
>>> for line in urllib2.urlopen(url).read().splitlines():
>>>     values = line.split()
>>>     if len(values) == 10:
>>>         primes.extend(values)
>>> print primes[1000-1]
>>
>> Nice, but you can do better.
>>
> import gmpy
> n = 1
> for i in xrange(1000):
>>        n = gmpy.next_prime(n)
> print n
>> 7919
>
>With the help of the solutions given so far, I can do even better than that:
>
>n = 7919
>print n

>>> 7919
7919

?
-- 
http://mail.python.org/mailman/listinfo/python-list

Re: Program to compute and print 1000th prime number

[Andre Engels]

On Sat, Nov 7, 2009 at 6:40 PM, Mensanator  wrote:

>> Tongue in cheek solution:
>>
>> import urllib2
>>
>> url = 'http://primes.utm.edu/lists/small/1.txt'
>> primes = []
>> for line in urllib2.urlopen(url).read().splitlines():
>>     values = line.split()
>>     if len(values) == 10:
>>         primes.extend(values)
>> print primes[1000-1]
>
> Nice, but you can do better.
>
 import gmpy
 n = 1
 for i in xrange(1000):
>        n = gmpy.next_prime(n)
 print n
> 7919

With the help of the solutions given so far, I can do even better than that:

n = 7919
print n


-- 
André Engels, andreeng...@gmail.com
-- 
http://mail.python.org/mailman/listinfo/python-list

Re: Program to compute and print 1000th prime number

[John Posner]

Robert P. J. Day said:

  the ubiquitous sieve of eratosthenes requires you to pre-specify
your maximum value, after which -- once the sieve completes -- all you
know is that you have all of the prime numbers up to n.  whether
you'll have 1000 of them isn't clear, which means that you might have
to start all over with a larger maximum value.  (being able to
directly determine the n'th prime number would solve a *lot* of prime
number problems. :-)

  
In April of this year, members of this forum helped me to devise a 
prime-number iterator [1]. So here's a simple solution for the OP:


#---
from itertools import ifilter, count

# create iterator
prime_iter = ifilter(
   lambda n, P=[]: all(n%p for p in P) and not P.append(n),
   count(2))

# throw away lots of primes
for i in range(999):   
   prime_iter.next()
  
# here's the one we want

print prime_iter.next()  #7919
#---

I don't think this is a solution that a course instructor would expect, 
though!


As mentioned in [1], optimizations of this algorithm (using 
itertools.takewhile() and/or caching previously-computed squares) are 
still at cl1p.net [2].


-John

[1]  http://mail.python.org/pipermail/python-list/2009-April/177415.html

[2]  http://www.cl1p.net/python_prime_generators


<http://cl1p.net/python_prime_generators/>



--
http://mail.python.org/mailman/listinfo/python-list

Re: Program to compute and print 1000th prime number

[Mensanator]

On Nov 7, 11:23 am, Raymond Hettinger  wrote:
> > > On Nov 7, 2009, at 9:44 AM, Ray Holt wrote:
>
> > >       I am taking the MIT online course Introduction to Computer Science 
> > > and
> > >       Programming. I have a assignment to write a program to compute and 
> > > print
> > >       the 1000th. prime number. Can someone give me some leads on the 
> > > correct
> > >       code? Thanks, Ray
>
> Tongue in cheek solution:
>
> import urllib2
>
> url = 'http://primes.utm.edu/lists/small/1.txt'
> primes = []
> for line in urllib2.urlopen(url).read().splitlines():
>     values = line.split()
>     if len(values) == 10:
>         primes.extend(values)
> print primes[1000-1]

Nice, but you can do better.

>>> import gmpy
>>> n = 1
>>> for i in xrange(1000):
n = gmpy.next_prime(n)
>>> print n
7919

>
> Raymond

-- 
http://mail.python.org/mailman/listinfo/python-list

Re: Program to compute and print 1000th prime number

[Xavier Ho]

On Sun, Nov 8, 2009 at 12:44 AM, Ray Holt  wrote:

>  I have a assignment to write a program to compute and print the 1000th.
> prime number. Can someone give me some leads on the correct code?
>

Ray, if you really want an answer out of this list, you'll have to at least
show us what efforts you've put into solving this problem. Perhaps if you
post your code that doesn't quite work, we can make suggestions on how to
improve/fix it. Other than that, it's generally considered bad karma to give
any kind of code, and we need to know where you are.

my 2c,
Xavier
-- 
http://mail.python.org/mailman/listinfo/python-list

Re: Program to compute and print 1000th prime number

[Robert P. J. Day]

On Sat, 7 Nov 2009, Raymond Hettinger wrote:

> > > On Nov 7, 2009, at 9:44 AM, Ray Holt wrote:
> >
> > >       I am taking the MIT online course Introduction to Computer
> > > Science and       Programming. I have a assignment to write a
> > > program to compute and print       the 1000th. prime number. Can
> > > someone give me some leads on the correct       code? Thanks,
> > > Ray
>
> Tongue in cheek solution:
>
> import urllib2
>
> url = 'http://primes.utm.edu/lists/small/1.txt'
> primes = []
> for line in urllib2.urlopen(url).read().splitlines():
> values = line.split()
> if len(values) == 10:
> primes.extend(values)
> print primes[1000-1]

  reminds me of a variation of an old joke:  using nothing but this
barometer, determine the height of that building.

  answer:  go to the building manager and say, "i'll give you this
really neat barometer if you tell me how tall this building is."

rday
--


Robert P. J. Day   Waterloo, Ontario, CANADA

Linux Consulting, Training and Kernel Pedantry.

Web page:  http://crashcourse.ca
Twitter:   http://twitter.com/rpjday
-- 
http://mail.python.org/mailman/listinfo/python-list

Re: Program to compute and print 1000th prime number

[Raymond Hettinger]

> > On Nov 7, 2009, at 9:44 AM, Ray Holt wrote:
>
> >       I am taking the MIT online course Introduction to Computer Science and
> >       Programming. I have a assignment to write a program to compute and 
> > print
> >       the 1000th. prime number. Can someone give me some leads on the 
> > correct
> >       code? Thanks, Ray

Tongue in cheek solution:

import urllib2

url = 'http://primes.utm.edu/lists/small/1.txt'
primes = []
for line in urllib2.urlopen(url).read().splitlines():
values = line.split()
if len(values) == 10:
primes.extend(values)
print primes[1000-1]


Raymond
-- 
http://mail.python.org/mailman/listinfo/python-list

Re: Program to compute and print 1000th prime number

[Robert P. J. Day]

On Sat, 7 Nov 2009, sstein...@gmail.com wrote:

>
> On Nov 7, 2009, at 9:44 AM, Ray Holt wrote:
>
>   I am taking the MIT online course Introduction to Computer Science and
>   Programming. I have a assignment to write a program to compute and print
>   the 1000th. prime number. Can someone give me some leads on the correct
>   code? Thanks, Ray
>
>
> Copying code != doing an assignment.  Try Knuth.

  i was going to say much the same, but it's also worth pointing out
that, using standard techniques, there is no straightforward way to
print the n'th prime number, given some initial value of n.

  the ubiquitous sieve of eratosthenes requires you to pre-specify
your maximum value, after which -- once the sieve completes -- all you
know is that you have all of the prime numbers up to n.  whether
you'll have 1000 of them isn't clear, which means that you might have
to start all over with a larger maximum value.  (being able to
directly determine the n'th prime number would solve a *lot* of prime
number problems. :-)

  and given that one can google and, in seconds, have the solution, i
feel no guilt in referring to
http://code.activestate.com/recipes/366178/.

rday
--


Robert P. J. Day   Waterloo, Ontario, CANADA

Linux Consulting, Training and Kernel Pedantry.

Web page:  http://crashcourse.ca
Twitter:   http://twitter.com/rpjday
-- 
http://mail.python.org/mailman/listinfo/python-list

Re: Program to compute and print 1000th prime number

[sstein...@gmail.com]

On Nov 7, 2009, at 9:44 AM, Ray Holt wrote:

I am taking the MIT online course Introduction to Computer Science  
and Programming. I have a assignment to write a program to compute  
and print the 1000th. prime number. Can someone give me some leads  
on the correct code? Thanks, Ray


Copying code != doing an assignment.  Try Knuth.

S


-- 
http://mail.python.org/mailman/listinfo/python-list

Program to compute and print 1000th prime number

[Ray Holt]

I am taking the MIT online course Introduction to Computer Science and
Programming. I have a assignment to write a program to compute and print the
1000th. prime number. Can someone give me some leads on the correct code?
Thanks, Ray
-- 
http://mail.python.org/mailman/listinfo/python-list

Re: Problem with returning prime number in a simple calculation program

[Steven D'Aprano]

On Sat, 03 Mar 2007 15:36:36 -0800, QHorizon wrote:

> Hello, I'm new to Python (I've learned everything up to iterators so
> far) and fairly new to Programming.  This would be my first real
> program:
> 
> #Coordinate Geometry (The whole program is not shown)
> 
> import math
> import sys
> 
> print "Welcome to the Coordinate Geometry Calculator!"
> print "Type 'terms' for a list of commands"
> 
> def main():

[snip big boring series of if...elif... statements]

You're eventually going to run into a run time recursion error if you run
that for long enough. Can you see why?

A better way to do a command loop is something like this:


def bad_command():
# called when the user enters an unrecognized command
print "Unknown command, please try again"

class QuitException(Exception):
# used for exiting the loop
pass


def main():
# Make a "dispatch table" that maps the name of a command 
# (as typed by the user) with a function to call.
dispatcher = {'slope': do_slope,
  'primes': do_primes,
  'quit': do_quit,
  # ... and more here
 }
try:
# loop forever (until we jump out of it)
while True:
cmd = get_command_from_user()
# you have to write get_command_from_user yourself
func = dispatcher.get(cmd, bad_command)
result = func()
print result
except QuitException:
print "Goodbye, come again soon!"


Now you just need to define your individual functions do_slope, do_primes,
etc. The only "special" one is do_quit.

def do_quit():
raise QuitException


Now let's look at the do_primes function. (You call it "prime".)

> def prime():
>   num = input("Number ")

That's a good way to have malicious users do really, really really bad
things to your PC.

Safer is to do this:

num = int(raw_input("Number "))

>   i = num - 1
>   divcounter = 0
>   while i > 1:
>   if num % i != 0:
>   divcounter += 1
>   i -= 1

That's an inefficient algorithm, if it even works. I'm not sure that it
works, and I'm too lazy to find out :)


>   if divcounter == num - 2:
>   print num, "is a prime number"
>   else:
>   print num, "is not a prime number"

This will only work if divcounter happens to equal the original number
less two. If it equals something else, nothing will be printed.

Here's a simple algorithm to check if a number is prime.

# Warning: untested.
def do_primes():
num = int(raw_input("Number ")
if num <= 1:
return "%n is not prime" % num
if num == 2:
return "%n is prime" % num
elif num % 2 == 0:
# even numbers other than 2 aren't prime
return "%n is not prime" % num
for i in range(3, num, 2):
if num % i == 0:
return "%n is not prime" % num
return "%n is prime" % num


Now, this is deliberately not an efficient algorithm. There are things you
can do to make it more efficient, or you can re-write it completely.
The thing to remember is, don't PRINT the result, RETURN it. Your
do_primes() function should only calculate the result, and pass that
result up to the main loop for printing (or writing to a text file, or
emailing, or whatever).

Have fun!



-- 
Steven.

-- 
http://mail.python.org/mailman/listinfo/python-list

Re: Problem with returning prime number in a simple calculation program

[Bjoern Schliessmann]

[EMAIL PROTECTED] wrote:
> [reformatted indentation]
> def prime():
> num = input("Number ")
> i = num - 1
> divcounter = 0
> while i > 1:
> if num % i != 0
> divcounter += 1 
> i -= 1
> if divcounter == num - 2:
> print num, "is a prime number"
> else:
> print num, "is not a prime number"
> [...]
> As it says in the title, I'm having trouble with the prime number
> function.  It will print the sentence if the number is prime, but
> it if isn't, the program goes into a state in the terminal where
> the program never ends and you can just keep on typing.  

Sure thing. You designed the function to behave this way.

Look at the while loop -- especially think what happens if 
(num % i == 0). i will never be decremented then and the function
will not terminate.

Try inserting print statements for debugging if you don't get what I
meant here.

> Maybe the else statement is ineffective?

No one can read your thoughts. In which way effective?

Regards,


Björn

-- 
BOFH excuse #86:

Runt packets

-- 
http://mail.python.org/mailman/listinfo/python-list

Problem with returning prime number in a simple calculation program

[QHorizon]

Hello, I'm new to Python (I've learned everything up to iterators so
far) and fairly new to Programming.  This would be my first real
program:

#Coordinate Geometry (The whole program is not shown)

import math
import sys

print "Welcome to the Coordinate Geometry Calculator!"
print "Type 'terms' for a list of commands"

def main():
print
command = raw_input("Command? ")
if command == "terms":
terms()
main()
elif command == "distance":
distance()
main()
elif command == "slope":
slope()
main()
elif command == "endpoint":
endpoint()
main()
elif command == "midpoint":
midpoint()
main()
elif command == "prime":
prime()
main()
elif command == "quit":
sys.exit
else:
print "Not a valid command"
main()

#...Declaring functions here...

def prime():
num = input("Number ")
i = num - 1
divcounter = 0
while i > 1:
if num % i != 0:
    divcounter += 1
i -= 1
    if divcounter == num - 2:
print num, "is a prime number"
    else:
print num, "is not a prime number"

#Start the program
main()

As it says in the title, I'm having trouble with the prime number
function.  It will print the sentence if the number is prime, but it
if isn't, the program goes into a state in the terminal where the
program never ends and you can just keep on typing.  Maybe the else
statement is ineffective?  Any ideas on how to fix this?

-- 
http://mail.python.org/mailman/listinfo/python-list

Re: Shortest prime number program

[Tim Hochberg]

In the spirit of pointless pessimization and obfuscation I have crushed 
something very similar to Alex Martelli's eratosthenes function onto a 
single line. It's truly monstrous, but somewhat entertaining [Some 
preemptive linebreaks added]:

def short():import itertools as it;D={};g=D.get;return (
q for q in it.count(2) if
D.__setitem__(it.dropwhile(D.__contains__, 
xrange(g(q,q)+q,2**30,g(q,q))).next(),g(q,q))
or q not in D and D.pop(q,1))


I'm sure there's a lesson to this somewhere. Something like I need to 
find something better to do with my spare time.

-tim

-- 
http://mail.python.org/mailman/listinfo/python-list

Re: Shortest prime number program

[Christoph Zwerschke]

Tim Hochberg wrote:
> from itertools import count, ifilter
> def sieve(s=count(2)):
>  while 1:p=s.next();s=ifilter(p.__rmod__,s);yield p

Nice!

-- Christoph
-- 
http://mail.python.org/mailman/listinfo/python-list

Re: Shortest prime number program

[Tim Hochberg]

While not nearly the shortest proposed thus far, I'm fond of:

from itertools import count, ifilter
def sieve(s=count(2)):
  while 1:p=s.next();s=ifilter(p.__rmod__,s);yield p

It will generate quite a large number of primes before blowing up (at 
least 50,000 primes, p=611,957) and it's much faster than the other 
submissions thus far that can generate a more or less arbitrary number 
of primes. It's still much slower than Alex Martelli's version in the 
cookbook though.

[And yes I know that you can shave off one character by importing 
ifilter as i, but that's too much ick for too little gain. There may 
well be other, more fruitful ways to compact it though]

-tim

-- 
http://mail.python.org/mailman/listinfo/python-list

Re: Shortest prime number program

[Ralf Muschall]

Christoph Zwerschke wrote:
> [EMAIL PROTECTED] schrieb:
>> How about:

>> [2]+[x for x in range(1,99) if 2**x%x==2]

> If the range goes beyond 340, it also gives non-primes...

[2,3]+[x for x in range(1,99) if 2**x%x==2 and 3**x%x==3]
[2,3,5]+[x for x in range(1,99) if 2**x%x==2 and 3**x%x==3 and 5**x%x==5]

SCNR, Ralf

PS: They both break at 561, and further strengthening of the
condition will not help.  Manual loop unrolling as follows works:

[2,3,... ]+[x for x in range(1,99) if False]

For sufficiently small values of 99, this will also be a rather
short program.
-- 
http://mail.python.org/mailman/listinfo/python-list

Re: Shortest prime number program

[swisscheese]

> 42
Make that 41 and 40.

-- 
http://mail.python.org/mailman/listinfo/python-list

Re: Shortest prime number program

[bearophileHUGS]

This is a little shorter :-)

[2]+[x for x in range(2,99)if 2**x%x==2] 

Bye,
bearophile

-- 
http://mail.python.org/mailman/listinfo/python-list

Re: Shortest prime number program

[swisscheese]

> [2]+[x for x in range(1,99) if 2**x%x==2]

42 - brilliant!
41:
[2]+[x for x in range(1,99)if 2**x%x==2]
... although it appears Christoph is right that it's not scalable.

-- 
http://mail.python.org/mailman/listinfo/python-list

Re: Shortest prime number program

[Jeffrey Schwab]

[EMAIL PROTECTED] wrote:
> swisscheese wrote:
> 
>>r=range(2,99)
>>m=[x*y for x in r for y in r]
>>[x for x in r if not x in m]
> 
> 
> How about:
> 
> [2]+[x for x in range(1,99) if 2**x%x==2]

43.

I'll be chewing on this one for a while.  Thank you. :)
-- 
http://mail.python.org/mailman/listinfo/python-list

Re: Shortest prime number program

[Christoph Zwerschke]

[EMAIL PROTECTED] schrieb:
> How about:
> 
> [2]+[x for x in range(1,99) if 2**x%x==2]

If the range goes beyond 340, it also gives non-primes...

-- Christoph
-- 
http://mail.python.org/mailman/listinfo/python-list

Re: Shortest prime number program

[dickinsm]

swisscheese wrote:
>
> r=range(2,99)
> m=[x*y for x in r for y in r]
> [x for x in r if not x in m]

How about:

[2]+[x for x in range(1,99) if 2**x%x==2]

Mark

-- 
http://mail.python.org/mailman/listinfo/python-list

Re: Shortest prime number program

[Grant Edwards]

On 2006-02-11, swisscheese <[EMAIL PROTECTED]> wrote:
>>You can save two bytes with
>
> 56 - nice catch.
> 55:
> r=range(2,99)
> [x for x in r if sum(x%d<1 for d in r)<2]

And if this were FORTRAN:

r=range(2,99)
[xforxinrifsum(x%d<1fordinr)<2]

;)

-- 
Grant Edwards   grante Yow!  Hmmm... a CRIPPLED
  at   ACCOUNTANT with a FALAFEL
   visi.comsandwich is HIT by a
   TROLLEY-CAR...
-- 
http://mail.python.org/mailman/listinfo/python-list

Re: Shortest prime number program

[Ian Bygrave]

On Sat, 11 Feb 2006 13:33:58 +, Ian Bygrave wrote:

> Well, given a hypothetical new function 'sieve'

which should have been:

def sieve(f,l):
if not l:
return l
head,tail=l[0],l[1:]
def filter_func(x):
return f(x,head)
tail=filter(filter_func,tail)
return [head]+sieve(f,tail)

> The prime generation can be reduced to:
> 
> from operator import *
> sieve(mod,range(2,99))

--Ian Bygrave

-- 
http://mail.python.org/mailman/listinfo/python-list

Re: Shortest prime number program

[Ian Bygrave]

On Sat, 11 Feb 2006 12:43:23 +, Ian Bygrave wrote:
> p,r=[],range(2,99)
> while r:p,r=p+r[:1],[x for x in r if x%r[0]]
> 
> And the result's in p.

Well, given a hypothetical new function 'sieve'

def sieve(f,l):
if not l:
return l
head,tail=l[0],l[1:]
def filter_func(x):
return f(x,head)
tail=filter(filter_func,tail)
return [head]+tail

The prime generation can be reduced to:

from operator import *
sieve(mod,range(2,99))

Is there any precedent for such a function, or any other uses?
 
--Ian Bygrave

-- 
http://mail.python.org/mailman/listinfo/python-list

Re: Shortest prime number program

[[EMAIL PROTECTED]]

swisscheese wrote:
> I figured someone out there must have written a minimal code size prime
> number generator. I did not find one after a bit of searching around.
> For primes up to 100 the best I could do was 70 characters (including
> spaces):
>
> r=range(2,99)
> m=[x*y for x in r for y in r]
> [x for x in r if not x in m]

import gmpy
p=2
while p<99:p=gmpy.next_prime(p)

-- 
http://mail.python.org/mailman/listinfo/python-list

Re: Shortest prime number program

[swisscheese]

>You can save two bytes with

56 - nice catch.
55:
r=range(2,99)
[x for x in r if sum(x%d<1 for d in r)<2]

-- 
http://mail.python.org/mailman/listinfo/python-list

Re: Shortest prime number program

[Martin v. Löwis]

You can save two bytes with
r=range(2,99)
[x for x in r if sum(x%d==0 for d in r)<2]
-- 
http://mail.python.org/mailman/listinfo/python-list

Re: Shortest prime number program

[Ian Bygrave]

On Sat, 11 Feb 2006 02:03:46 -0800, swisscheese wrote:

> I figured someone out there must have written a minimal code size prime
> number generator. I did not find one after a bit of searching around.
> For primes up to 100 the best I could do was 70 characters (including
> spaces):
> 
> r=range(2,99)
> m=[x*y for x in r for y in r]
> [x for x in r if not x in m]

I swore I'd never play Python golf.

p,r=[],range(2,99)
while r:p,r=p+r[:1],[x for x in r if x%r[0]]

And the result's in p.

--Ian Bygrave

-- 
http://mail.python.org/mailman/listinfo/python-list

Re: Shortest prime number program

[swisscheese]

At 58, very nice :-) Building on yours we get 57:
r=range(2,99)
[x for x in r if sum([x%d==0 for d in r])<2]

-- 
http://mail.python.org/mailman/listinfo/python-list

Re: Shortest prime number program

[Mitja Trampus]

swisscheese wrote:
> I figured someone out there must have written a minimal code size prime
> number generator. I did not find one after a bit of searching around.
> For primes up to 100 the best I could do was 70 characters (including
> spaces):
> 
> r=range(2,99)
> m=[x*y for x in r for y in r]
> [x for x in r if not x in m]

A more straightforward and somewhat shorter solution:

r=range(2,99)
[x for x in r if [x%d for d in r].count(0)<2]

I'm sure it can be made shorter still.
-- 
http://mail.python.org/mailman/listinfo/python-list

Shortest prime number program

[swisscheese]

I figured someone out there must have written a minimal code size prime
number generator. I did not find one after a bit of searching around.
For primes up to 100 the best I could do was 70 characters (including
spaces):

r=range(2,99)
m=[x*y for x in r for y in r]
[x for x in r if not x in m]

-- 
http://mail.python.org/mailman/listinfo/python-list

Re: prime number

[Cameron Laird]

In article <[EMAIL PROTECTED]>,
lostinpython <[EMAIL PROTECTED]> wrote:
>It is a homework assignment from a book but not for a class.  I'm
>trying to teach my self some basic programming before I have to take it
>in college.  If I show enough understanding of the subject, my advisor
>will let me forgo Intro. to Programming and go into Intro. to C++.
>What civil engineers need with all this programming is beyond me.  We
>have to learn another language to program our CADD software, which I
>find much easier than this.  But needless to say, I'm stumped on this
.
.
.
What's the crack about first place being a paid weekend vacation 
in Philadelpha, and second place five days?  Without knowledge of
the particulars of your situation, "Intro. to C++" sounds to me
more like punishment than incentive.

And I like C++.

One important instinct for your programming career is sensitivity
to "easier".  I strongly suspect, though, that there are real
values in "basic programming" that your "CADD software" has not 
yet taught you.
-- 
http://mail.python.org/mailman/listinfo/python-list

Alternative history (was: prime number)

[Cameron Laird]

In article <[EMAIL PROTECTED]>, Mike Meyer  <[EMAIL PROTECTED]> wrote:
.
.
.
>If it isn't a homework assignment, and you're honestly in such, then
>you should know there's been a lot of research in this area, because
>primes are important in cryptographic applications. Once again, google
.
.
.
There's been a lot of research in this area because some minds
burn to grasp the beauty of number theory, and can't stop think-
ing of Number despite blindness, hunger, family, political 
oppression, and the other frailties to which humans are prone.
-- 
http://mail.python.org/mailman/listinfo/python-list

Re: prime number

[Mikael Olofsson]

lostinpython wrote:
> What civil engineers need with all this programming is beyond me.  We
> have to learn another language to program our CADD software, which I
> find much easier than this.  

According to my experience, almost every engineer - civil or not - uses 
programming at least occationally. So every engineering education 
program should involve at least some programming.

/Mikael Olofsson

Universitetslektor (Senior Lecturer [BrE], Associate Professor [AmE])
Linköpings universitet

---
E-Mail:  [EMAIL PROTECTED]
WWW: http://www.dtr.isy.liu.se/en/staff/mikael
Phone:   +46 - (0)13 - 28 1343
Telefax: +46 - (0)13 - 28 1339
---
Linköpings kammarkör: www.kammarkoren.com   Vi söker tenorer och basar!
-- 
http://mail.python.org/mailman/listinfo/python-list

Re: prime number

[Dale Hagglund]

Sigh ... one of my intermediate versions of is_prime() returns True if
the n is *not* prime, and false otherwise.  The final version is
correct, though.

Dale.

-- 
http://mail.python.org/mailman/listinfo/python-list

Re: prime number

[Dale Hagglund]

lostinpython> I'm having trouble writing a program that figures
lostinpython> out a prime number.  Does anyone have an idea on how
lostinpython> to write it?  

[I can't quite tell from your posts what your level of programming
knowledge is, so I've aimed low.  If this was wrong, please accept my
apologies. --rdh]

It's not quite clear precisely what the problem is. Do you want to
find all primes less than some number N, or find the prime
factorization of some input number, or something else altogether?  Are
there any other constraints?  Ie, does the program have to be
recursive?

I'm going to assume that you want to find all primes less than N, and
that are no constraints on the form of the program.  

First, pretend you have a function called "is_prime".  It will look
something like this:

def is_prime(n):
# return True if n is prime, False otherwise
# magic goes here

If we had this function, the our main program would look something
like this:

N = 20
for n in range(1, N+1):
if is_prime(n):
   print n

NOTE: range(1,N+1) returns a list of numbers from 1 to N inclusive.

The question now is how to fill in the missing part of is_prime.  In
your original post, you noted that n>2 is prime if no number between 2
and sqrt(n) inclusive divides into n evenly.

This tells us that we have to test a list of possible factors for
divisibility into n.  Ignoring, for a little while, how we figure out
the possible factors, we can now expand is_prime as follows:

def is_prime(n):
# return 1 if n is prime, 0 otherwise
from math import sqrt
for i in possible_factors:
# if i divides n, n isn't prime
# if no i divided into n, ie, we fell out of the loop, 
# n is prime

The possible factor i divides into n if n % i == 0.  Once we've
decided that n is or isn't prime, we can just return True or False
respectively.  Adding these details:

def is_prime(n):
# return 1 if n is prime, 0 otherwise
from math import sqrt
for i in possible_factors:
if n % i == 0:
return True
return False   

The final step is to figure out the list of possible factors.  By the
definition, this is the list of integers from 2 to the integer value
of sqrt(n), inclusive.  To get this list, we can use the range
function again, assuming that sqrt(n) to compute the square root for
us.  The list of possible factors is given by

range(2, int(sqrt(n)) + 1)

The final trick to is to get the definition of sqrt.  It turns out
that this function is defined in the math module.  Adding the bit of
syntax needed to access the sqrt function, we have:

def is_prime(n):
# return 1 if n is prime, 0 otherwise
from math import sqrt
for i in range(2, int(sqrt(n)) + 1):
if n % i == 0:
return False
return True

Put together with the main program above, this will print out a list
as follows:

1
2
3
5
7
11
13
17
19

However, there's a slight problem here.  By definition, 1 is not a
prime.  We could fix this a couple of ways.  Either we could change
the main program not to start its range with 1, or we can fix
is_prime.  The latter is simple:

def is_prime(n):
# return 1 if n is prime, 0 otherwise
from math import sqrt
if n == 1:
return False
for i in range(2, int(sqrt(n)) + 1):
if n % i == 0:
return False
return True

Another algorithm mentioned in the followups to your posting is the
Sieve of Eratosthenes, named for its ancient Greek discoverer.  You
can find a description of the Sieve in many places on the web.  Trying
to implement it might be a good next step.

Dale.

-- 
http://mail.python.org/mailman/listinfo/python-list

Re: prime number

[Rocco Moretti]

lostinpython wrote:
> But needless to say, I'm stumped on this
> problem.  I keep ending up in a never ending loop.

I've been told that the trick with recursion/iteration is to always 
determine what your ending condition is first, and then construct the 
body of the recursion/loop to reach that ending condition eventually. If 
you post the specific code which is giving you problems, people here can 
point out why you're missing the exit.
-- 
http://mail.python.org/mailman/listinfo/python-list

Re: prime number

[phil]

> What civil engineers need with all this programming is beyond me. 


One of my best friends and expartner and top civil-structural
engineers in the country (he built Dallas Reunion Arena and many
other complex structures) was an ace programmer in many languages.

He was not willing to just accept the results of canned packages,
he wanted to know where the answers came from and make software
that made sense to his engineers.

I presume you are young and if you wish to be an engineer and not
a salesman you must be eaten up with the desire to know
"How Stuff Works".  Computers are ubiquitous in engineering
and if you want to be the best, learn how they work.

-- 
http://mail.python.org/mailman/listinfo/python-list

Re: prime number

[Brian van den Broek]

lostinpython said unto the world upon 2005-05-30 02:50:
> It is a homework assignment from a book but not for a class.  I'm
> trying to teach my self some basic programming before I have to take it
> in college.  If I show enough understanding of the subject, my advisor
> will let me forgo Intro. to Programming and go into Intro. to C++.
> What civil engineers need with all this programming is beyond me.  We
> have to learn another language to program our CADD software, which I
> find much easier than this.  But needless to say, I'm stumped on this
> problem.  I keep ending up in a never ending loop.
> 
> Shanna

Hi Shanna,

Since you are just beginning, I'd like to recommend the tutor list 
. It is not that 
newcomers are not welcome here. But the folks who populate the tutor 
list are particularly good at answering neophytes' questions at the 
level.

Since you've got some code together, even though it isn't doing what 
you want, you've already got a decent start for getting help. Post the 
question and the code to the tutor list and I'd not be surprised if 
you will soon be well on your way to solving your problem.

Best,

Brian vdB
Who owes much of what he knows about Python to the tutor list.

-- 
http://mail.python.org/mailman/listinfo/python-list

Re: prime number

[lostinpython]

It is a homework assignment from a book but not for a class.  I'm
trying to teach my self some basic programming before I have to take it
in college.  If I show enough understanding of the subject, my advisor
will let me forgo Intro. to Programming and go into Intro. to C++.
What civil engineers need with all this programming is beyond me.  We
have to learn another language to program our CADD software, which I
find much easier than this.  But needless to say, I'm stumped on this
problem.  I keep ending up in a never ending loop.

Shanna

Mike Meyer wrote:
> "lostinpython" <[EMAIL PROTECTED]> writes:
> > I'm having trouble writing a program that figures out a prime number.
> > Does anyone have an idea on how to write it?  All I know is that n > 2
> > is prim if no number between 2 and sqrt of n (inclusivly) evenly
> > divides n.
>
> How about this (untested):
>
> import sys
> import subprocess
>
> primes = subprocess.Popen(["primes", sys.argv[1], sys.argv[1]],
> stdout=subprocess.PIPE).stdout.readlines()
> if primes:
>print sys.argv[1], "prime"
> else:
>print sys.argv[1], "not prime"
>
> Seriously, this sounds like a homework assignment. Google for "sieve
> of eratosthenes". The BSD "primes" program I used in the above is an
> implementation of that in C.
>
> If it isn't a homework assignment, and you're honestly in such, then
> you should know there's been a lot of research in this area, because
> primes are important in cryptographic applications. Once again, google
> is a good place to start on looking for recent research on the subject.
>
> --
> Mike Meyer <[EMAIL PROTECTED]>
> http://www.mired.org/home/mwm/
> Independent WWW/Perforce/FreeBSD/Unix consultant, email for more information.

-- 
http://mail.python.org/mailman/listinfo/python-list

Re: prime number

[Mike Meyer]

"lostinpython" <[EMAIL PROTECTED]> writes:
> I'm having trouble writing a program that figures out a prime number.
> Does anyone have an idea on how to write it?  All I know is that n > 2
> is prim if no number between 2 and sqrt of n (inclusivly) evenly
> divides n.

How about this (untested):

import sys
import subprocess

primes = subprocess.Popen(["primes", sys.argv[1], sys.argv[1]],
stdout=subprocess.PIPE).stdout.readlines()
if primes:
   print sys.argv[1], "prime"
else:
   print sys.argv[1], "not prime"

Seriously, this sounds like a homework assignment. Google for "sieve
of eratosthenes". The BSD "primes" program I used in the above is an
implementation of that in C.

If it isn't a homework assignment, and you're honestly in such, then
you should know there's been a lot of research in this area, because
primes are important in cryptographic applications. Once again, google
is a good place to start on looking for recent research on the subject.

 http://www.mired.org/home/mwm/
Independent WWW/Perforce/FreeBSD/Unix consultant, email for more information.
-- 
http://mail.python.org/mailman/listinfo/python-list

Re: prime number

[Tim Leslie]

On 29 May 2005 19:55:32 -0700, lostinpython
<[EMAIL PROTECTED]> wrote:
> I'm having trouble writing a program that figures out a prime number.
> Does anyone have an idea on how to write it?  All I know is that n > 2
> is prim if no number between 2 and sqrt of n (inclusivly) evenly
> divides n.

This sounds remarkably like a homework problem, so I'm not going to
give you a full answer. Perhaps if you could be more specific about
which part's giving you trouble we could help you out with that.

If it finding square roots? is it checking for divisibility? is it
getting the loop to run through correctly? Is it some other problem?

Tim

> 
> --
> http://mail.python.org/mailman/listinfo/python-list
>
-- 
http://mail.python.org/mailman/listinfo/python-list

prime number

[lostinpython]

I'm having trouble writing a program that figures out a prime number.
Does anyone have an idea on how to write it?  All I know is that n > 2
is prim if no number between 2 and sqrt of n (inclusivly) evenly
divides n.

-- 
http://mail.python.org/mailman/listinfo/python-list