Re: Code for finding the 1000th prime
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 -- http://mail.python.org/mailman/listinfo/python-list
Re: Code for finding the 1000th prime
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(1): if i==7919: # Found it! print i ;-) -- Carsten Haese http://informixdb.sourceforge.net -- http://mail.python.org/mailman/listinfo/python-list
Re: Code for finding the 1000th prime
2009/11/15 mrholtsr mrhol...@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. -- http://mail.python.org/mailman/listinfo/python-list
Re: Code for finding the 1000th prime
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
Re: Code for finding the 1000th prime
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 -- http://mail.python.org/mailman/listinfo/python-list
Re: Code for finding the 1000th prime
On Tue, Nov 17, 2009 at 9:27 AM, Diez B. Roggisch de...@nospam.web.de wrote: Stefan Behnel wrote: Robert P. J. Day, 15.11.2009 15:44: 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. There's prior art for this algorithm: http://en.wikipedia.org/wiki/Bogosort 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. Cheers, Chris -- http://blog.rebertia.com -- http://mail.python.org/mailman/listinfo/python-list
Re: Code for finding the 1000th prime
In article aecf2132-05a9-4144-81a8-952bb435e...@a32g2000yqm.googlegroups.com, mrholtsr mrhol...@gmail.com 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 OK, newbie soccer is over. http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes Everything you need is in there. -- -Ed Falk, f...@despams.r.us.com http://thespamdiaries.blogspot.com/ -- http://mail.python.org/mailman/listinfo/python-list
Re: Code for finding the 1000th prime
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 Now for a serious answer ;-) The intent of the problem is that you write a function prime_n(n) that returns the nth prime, where 2 is the first. This is different from prime(n), which would return True/False depending on whether n is a prime or not. Then you are to execute prime_n(1000) and submit that. The person who set the problem expects that you will have learned and still remember the definition of prime numbers and a few basic facts about them. Or that you will look these up on a site such as Wikipedia. Since you are not taking a math course, you should expect that the basic facts will be enough. For this problem, the relevant fact is that there is no formula that will directly compute the nth prime from n. Instead, one must generate the first, the second, the third, , until reaching the nth. The easiest and direct way to do this is to use primes 1 to i to test whether counts greater than prime i are primes, until you find the (i+1)th prime. You may find references to the Sieve of Eratosthenes. It generates all the primes up to a certain number N by testing prime divisors in a different order. But to use it find the nth, one has to guess that some N will be larger than the nth, run the Sieve, and see whether you got the nth or have to try a larger value of N. For the 1000th, it turns out that N=1 works. In general picking an N such that N * log(N) is 'comfortably' larger than n will work. But this guessing is not actually necessary in Python which has *expandable* arrays. A different approach, at least as difficult, is to write a program that looks up the answer by accessing a public database of primes. http://en.wikipedia.org/wiki/List_of_primes lists some of these in its External Links section. Terry Jan Reedy -- http://mail.python.org/mailman/listinfo/python-list
Re: Code for finding the 1000th prime
On Nov 15, 10:02 am, Diez B. Roggisch de...@nospam.web.de wrote: mrholtsr schrieb: 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 Do you really think we are so retarded that we don't remember you posted the same question a week ago? Diez Mea Culpa. I didn't realize at the time that this group was the same as the newsletter. Won't do it again. -- http://mail.python.org/mailman/listinfo/python-list
Re: Code for finding the 1000th prime
On 15 Nov, 15:30, mrholtsr mrhol...@gmail.com 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 print 7919 -- http://mail.python.org/mailman/listinfo/python-list
Re: Code for finding the 1000th prime
mrholtsr schrieb: 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 Do you really think we are so retarded that we don't remember you posted the same question a week ago? Diez -- http://mail.python.org/mailman/listinfo/python-list
