Code for finding the 1000th prime

Discussion in 'Python' started by mrholtsr, Nov 15, 2009.

  1. mrholtsr

    mrholtsr Guest

    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
    mrholtsr, Nov 15, 2009
    #1
    1. Advertising

  2. 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.

    rday
    --

    ========================================================================
    Robert P. J. Day Waterloo, Ontario, CANADA

    Linux Consulting, Training and Kernel Pedantry.

    Web page: http://crashcourse.ca
    Twitter: http://twitter.com/rpjday
    ========================================================================
    Robert P. J. Day, Nov 15, 2009
    #2
    1. Advertising

  3. 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
    Diez B. Roggisch, Nov 15, 2009
    #3
  4. mrholtsr

    mrholtsr Guest

    On Nov 15, 10:02 am, "Diez B. Roggisch" <> 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.
    mrholtsr, Nov 16, 2009
    #4
  5. mrholtsr

    sturlamolden Guest

    On 15 Nov, 15:30, 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



    print "7919"
    sturlamolden, Nov 16, 2009
    #5
  6. 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
    Stefan Behnel, Nov 17, 2009
    #6
  7. 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
    Carsten Haese, Nov 17, 2009
    #7
  8. mrholtsr

    Himanshu Guest

    2009/11/15 mrholtsr <>:
    > 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.
    Himanshu, Nov 17, 2009
    #8
  9. mrholtsr

    Peter Otten Guest

    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
    Peter Otten, Nov 17, 2009
    #9
  10. 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
    Diez B. Roggisch, Nov 17, 2009
    #10
  11. mrholtsr

    Chris Rebert Guest

    On Tue, Nov 17, 2009 at 9:27 AM, Diez B. Roggisch <> 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
    Chris Rebert, Nov 17, 2009
    #11
  12. In article <>,
    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


    OK, newbie soccer is over.

    http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

    Everything you need is in there.

    --
    -Ed Falk,
    http://thespamdiaries.blogspot.com/
    Edward A. Falk, Nov 17, 2009
    #12
  13. mrholtsr

    Terry Reedy Guest


    >> 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=10000 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
    Terry Reedy, Nov 17, 2009
    #13
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Replies:
    0
    Views:
    656
  2. Shawn Milochik

    Re: [Tutor] Finding prime numbers

    Shawn Milochik, Sep 19, 2007, in forum: Python
    Replies:
    4
    Views:
    280
    Shawn Milochik
    Sep 20, 2007
  3. Robert P. J. Day
    Replies:
    5
    Views:
    2,633
    mrdeath5493
    Jan 17, 2011
  4. Neal
    Replies:
    2
    Views:
    381
  5. Jeremy Fischer
    Replies:
    0
    Views:
    175
    Jeremy Fischer
    Jan 16, 2005
Loading...

Share This Page