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 prime
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"
>
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" th
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
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
>>>
rom 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
>
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 ever
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
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 c
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 modul
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 "
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
he 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 inf
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
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 com
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
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
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
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
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,
an
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
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():
>
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:
>>
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
ompute 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/s
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 u
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
> > 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
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.
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
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
quot;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
= 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
>
():
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 numbe
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
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
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 fast
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
> 42
Make that 41 and 40.
--
http://mail.python.org/mailman/listinfo/python-list
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
> [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
[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
[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
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
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
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 [
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):
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
>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
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
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):
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
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
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
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 fo
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 ar
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 occationa
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
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
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 e
> 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 accep
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. t
quot; <[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
> > divi
"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
>
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 (inclusi
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
66 matches
Mail list logo
