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 -- http://mail.python.org/mailman/listinfo/python-list