Code for finding the 1000th prime
in [Python]
|
Prev: ANN: PyGUI 2.1
Next: SCGIServer and unusal termination
From: Stefan Behnel on 17 Nov 2009 08:00 Robert P. J. Day, 15.11.2009 15:44: > On Sun, 15 Nov 2009, mrholtsr wrote: > >> I am absolutely new to python and barely past beginner in programming. >> Also I am not a mathematician. Can some one give me pointers for >> finding the 1000th. prime for a course I am taking over the internet >> on Introduction to Computer Science and Programming. Thanks, Ray > > it's 7919. Now, all that's left to do is write a prime number generator (a random number generator will do, too, but writing a good one isn't easy), run it repeatedly in a loop, and check if the returned number is 7919. Once it compares equal, you can print the result and you're done. Stefan
From: Carsten Haese on 17 Nov 2009 09:33 Stefan Behnel wrote: > Robert P. J. Day, 15.11.2009 15:44: >> On Sun, 15 Nov 2009, mrholtsr wrote: >> >>> I am absolutely new to python and barely past beginner in programming. >>> Also I am not a mathematician. Can some one give me pointers for >>> finding the 1000th. prime for a course I am taking over the internet >>> on Introduction to Computer Science and Programming. Thanks, Ray >> it's 7919. > > Now, all that's left to do is write a prime number generator (a random > number generator will do, too, but writing a good one isn't easy), run it > repeatedly in a loop, and check if the returned number is 7919. Once it > compares equal, you can print the result and you're done. Just do a brute-force search: for i in range(10000): if i==7919: # Found it! print i ;-) -- Carsten Haese http://informixdb.sourceforge.net
From: Himanshu on 17 Nov 2009 10:41 2009/11/15 mrholtsr <mrholtsr(a)gmail.com>: > I am absolutely new to python and barely past beginner in programming. > Also I am not a mathematician. Can some one give me pointers for > finding the 1000th. prime for a course I am taking over the internet > on Introduction to Computer Science and Programming. Thanks, Ray > -- > http://mail.python.org/mailman/listinfo/python-list > Consider skipping such "mathematically oriented" exercises in an introductory course on python if targeted to a general audience.
From: Peter Otten on 17 Nov 2009 11:27 mrholtsr wrote: > I am absolutely new to python and barely past beginner in programming. > Also I am not a mathematician. Can some one give me pointers for > finding the 1000th. prime for a course I am taking over the internet > on Introduction to Computer Science and Programming. Thanks, Ray When you encounter a problem that you find hard try to split it into simpler subproblems. Example: To find the 1000th prime start with a program that finds all integers i = 1 while True: print i i = i + 1 If you run that it will print integers until you hit Ctrl-C. Python offers an elegant construct that helps you encapsulate the logic of a loop, called "generator". With that we can rewrite the all-integers program as def all_natural_numbers(): i = 1 while True: yield i i = i + 1 for i in all_natural_numbers(): print i Now let's tackle the next step: we want only prime numbers, but don't know how to check for them. How can we postpone that problem and still continue with our program? Easy: introduce a function where the check will ultimately go but have it do something that we do understand right now: def isprime(candidate): return candidate != 42 Why not check for candidate == 42? We would only ever get one "pseudo- prime", but we need at least 1000 of them. With the above bold assumption the program becomes def isprime(candidate): return candidate != 42 def all_natural_numbers(): i = 1 while True: yield i i = i + 1 for i in all_natural_numbers(): if isprime(i): print i While the actual output is a bit unorthodox we now have the structure to print all prime numbers. Again we can wrap the logic into a generator: def isprime(candidate): return candidate != 42 def all_natural_numbers(): i = 1 while True: yield i i = i + 1 def all_prime_numbers(): for i in all_natural_numbers(): if isprime(i): yield i for p in all_prime_numbers(): print p We are actually only interested in the 1000th prime. We can find that by counting over all prime numbers: i = 1 for p in all_prime_numbers(): if i == 1000: print p break i = i + 1 We can wrap this step in a function for future reuse: # all_natural_numbers(), all_prime_numbers(), # and isprime() as before def nth_item(items, n): i = 1 for item in items: if i == n: return item i = i + 1 # raise Exception("here be dragons") print nth_item(all_prime_numbers(), 1000) OK, we now have a nice clean python script that tells us that the 1000th prime number is 1001, a finding that will meet some opposition among mathematicians. Let's turn to wikipedia for help: """ a prime number (or a prime) is a natural number which has exactly two distinct natural number divisors: 1 and itself. .... The number 1 is by definition not a prime number. """ Translated into Python: def isprime(candidate): if candidate == 1: return False # 1 is not a prime for potential_divisor in range(2, candidate): if int(candidate/potential_divisor)*potential_divisor == candidate: # candidate could be divided by potential divisor # without rest, so it's not a prime return False # we didn't find a divisor for candidate # -- it must be a prime return True Now while this test for primality is not the most beautiful code I've ever written it should give you the correct result. As a first step to improve it have a look at the % ("modulo") operator in your textbook. Then try to reduce the number of potential divisors. Peter
From: Diez B. Roggisch on 17 Nov 2009 12:27
Stefan Behnel wrote: > Robert P. J. Day, 15.11.2009 15:44: >> On Sun, 15 Nov 2009, mrholtsr wrote: >> >>> I am absolutely new to python and barely past beginner in programming. >>> Also I am not a mathematician. Can some one give me pointers for >>> finding the 1000th. prime for a course I am taking over the internet >>> on Introduction to Computer Science and Programming. Thanks, Ray >> >> it's 7919. > > Now, all that's left to do is write a prime number generator (a random > number generator will do, too, but writing a good one isn't easy), run it > repeatedly in a loop, and check if the returned number is 7919. Once it > compares equal, you can print the result and you're done. That reminds me of the only algorithm I really invented myself: debil sort. It goes like this: L = <list of comparable items> while not sorted(L): p = generate_random_permutation(len(L)) L = apply_permutation(L, p) print L Great algorithm. Actually works. And the saddest thing: somebody out there certainly has written something like that by accident... I've spotted sorting in O(n^3) (with non-deterministic exceptional termination conditions) already in the wild. Diez |