Mailing List Archive: Python: Python

Program to compute and print 1000th prime number

Index | Next | Previous | View Threaded

mrholtsr at sbcglobal

Nov 7, 2009, 6:44 AM

Post #1 of 10 (2672 views)
Permalink

Program to compute and print 1000th prime number

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

ssteinerx at gmail

Nov 7, 2009, 6:49 AM

Post #2 of 10 (2643 views)
Permalink

Re: Program to compute and print 1000th prime number [In reply 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 someone give me some leads
> on the correct code? Thanks, Ray

Copying code != doing an assignment. Try Knuth.

S

rpjday at crashcourse

Nov 7, 2009, 7:21 AM

Post #3 of 10 (2644 views)
Permalink

Re: Program to compute and print 1000th prime number [In reply to]

On Sat, 7 Nov 2009, ssteinerX [at] gmail 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
========================================================================

python at rcn

Nov 7, 2009, 9:23 AM

Post #4 of 10 (2639 views)
Permalink

Re: Program to compute and print 1000th prime number [In reply 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 someone give me some leads on the correct
> > code? Thanks, Ray

Tongue in cheek solution:

import urllib2

url = 'http://primes.utm.edu/lists/small/10000.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

rpjday at crashcourse

Nov 7, 2009, 9:32 AM

Post #5 of 10 (2632 views)
Permalink

Re: Program to compute and print 1000th prime number [In reply to]

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/10000.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
========================================================================

contact at xavierho

Nov 7, 2009, 9:37 AM

Post #6 of 10 (2638 views)
Permalink

Re: Program to compute and print 1000th prime number [In reply to]

On Sun, Nov 8, 2009 at 12:44 AM, Ray Holt <mrholtsr [at] sbcglobal> 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

mensanator at aol

Nov 7, 2009, 9:40 AM

Post #7 of 10 (2636 views)
Permalink

Re: Program to compute and print 1000th prime number [In reply to]

On Nov 7, 11:23 am, Raymond Hettinger <pyt...@rcn.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
>
> Tongue in cheek solution:
>
> import urllib2
>
> url = 'http://primes.utm.edu/lists/small/10000.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

jjposner at optimum

Nov 7, 2009, 10:18 AM

Post #8 of 10 (2635 views)
Permalink

Re: Program to compute and print 1000th prime number [In reply to]

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

andreengels at gmail

Nov 7, 2009, 10:34 AM

Post #9 of 10 (2635 views)
Permalink

Re: Program to compute and print 1000th prime number [In reply to]

On Sat, Nov 7, 2009 at 6:40 PM, Mensanator <mensanator [at] aol> wrote:

>> Tongue in cheek solution:
>>
>> import urllib2
>>
>> url = 'http://primes.utm.edu/lists/small/10000.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, andreengels [at] gmail
--
http://mail.python.org/mailman/listinfo/python-list

wbrehaut at mcsnet

Nov 7, 2009, 2:43 PM

Post #10 of 10 (2635 views)
Permalink

Re: Program to compute and print 1000th prime number [In reply to]

On Sat, 7 Nov 2009 19:34:47 +0100, Andre Engels
<andreengels [at] gmail> wrote:

>On Sat, Nov 7, 2009 at 6:40 PM, Mensanator <mensanator [at] aol> wrote:
>
>>> Tongue in cheek solution:
>>>
>>> import urllib2
>>>
>>> url = 'http://primes.utm.edu/lists/small/10000.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

Index | Next | Previous | View Threaded

Interested in having your list archived? Contact Gossamer Threads