> 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. :-)
> > 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]
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
> > > 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):
> 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].
|
