Python while loop won't exit (Beginner)

Question

The while loop at the end doesn't exit and I can't figure out why.

import sys

def is_prime(n):
    if n == 3:
        return True
    elif n == 4:
        return False
    else:
        for i in xrange(2,n):
            if n % i == 0:
                return False
        return True

primes = [2, 3]

counter = int(raw_input("Which prime number would you like to find? "))

while len(primes) < counter:
    for i in xrange(primes[-1], sys.maxint):
        if is_prime(i):
            primes.append(i)

print(primes[-1])

wrt optimizations; there are also far more efficient algorithms for Primality test — James Mills
– James Mills, Commented May 5, 2015 at 3:09

Martin Konecny · Accepted Answer · 2015-05-05 03:09:09Z

4

The reason it won't exit is because your search space for potential primes numbers is way too big. Your desktop is not that fast! They have supercomputers trying to calculate this stuff.

for i in xrange(primes[-1], sys.maxint):

To start with, try changing this to something more reasonable:

for i in xrange(primes[-1], 10000):

You will see your loop does actually exit.

EDIT:

There are some nice optimizations you can add to this problem. First, you should increment by 2 to skip all even numbers:

for i in xrange(primes[-1], sys.maxint, 2):

Second, you only need to test for divisors up to the square root of the potential prime number.

for i in xrange(2,n**(0.5)):

The reason for this is that any two numbers whose product is n, one of those will always be less than the square root of n - therefore if you haven't found a divisor by the time you hit the square root of n, you can stop. This greatly reduces your search space for larger numbers.

edited May 5, 2015 at 3:09

answered May 5, 2015 at 3:03

Martin Konecny

59.9k20 gold badges144 silver badges159 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

abarnert Over a year ago

This isn't really the problem—and it's not a great solution, because it means getting the 8th prime is just as expensive as getting the 1229th, while getting the 1230th will go into an infinite loop.

conjenks Over a year ago

Got it! The issue was that I was not aware that the while condition does not get checked at the end of every for loop iteration. I was never trying to find that many prime numbers. A simple addition of a break after the primes.append(i) solved it, even with the ridiculous range. Lesson learned. Thanks!

Martin Konecny Over a year ago

@abarnert - you are correct. I missed the part where he is trying to find a specific prime number, not all of them. Can you briefly expand on the 1230th prime going into an infinite loop?

abarnert Over a year ago

@MartinKonecny: The 1230th prime number is 10007. So, the outer loop will see that you only have 1229 primes, the inner loop will go from 9974 to 10000 and see no new primes and exit, the outer loop will see that you only have 1229 primes, ad infinitum.

abarnert Over a year ago

Although I think he has another bug, where he'll just keep appending 9973 onto the list each time, in which case he will actually return, just with the wrong number (for any input >1229, it'll return 9973).

Community · Accepted Answer · 2017-05-23 11:58:26Z

1

As Martin Konecny's answer explains, your loop requires calculating all the primes up to sys.maxint, which takes a very, very long time (especially if you're on a 64-bit platform!).

But really, you don't need primes up to sys.maxint, or even primes up to 10000. With his solution, you're going to calculate the first 1229 primes even if you only need the first 7, which means it'll take way longer than necessary. Worse, you're only going to calculate the first 1229 primes, even if you need the 1400th, which means you'll end up in an infinite loop looking for the next prime under 10000 forever even though there are no more primes under 10000.

The key here is to break out of the inner loop as soon as possible, so you can get back to the outer loop. The inner loop is checking whether you have a big enough prime, which isn't relevant to your problem; the outer loop is checking whether you have enough primes. So you want to check the outer loop after each prime that you find.

One way to do that is to change the inner loop so it just breaks out after one prime, giving you a chance to check the len again:

while len(primes) < counter:
    for i in xrange(primes[-1], sys.maxint):
        if is_prime(i):
            primes.append(i)
            break

In fact, if you do this, you can even replace the limit with an infinite range, and it will still complete.

One more thing: You have a bug in the inner loop: xrange(primes[-1], sys.maxint) includes primes[-1]. And primes[-1] is obviously prime. So, you're just going to keep appending the same value over and over. You need a + 1 there.

So:

while len(primes) < counter:
    for i in itertools.count(primes[-1]+1)
        if is_prime(i):
            primes.append(i)
            break

A better solution to this problem would be to use a real prime sieve rather than a divisor test. A sieve effectively keeps a lookahead mapping of the next multiples of each prime found so far, so you can very quickly determine whether N is prime if you've already checked all the values up to N-1. But doing that is a much larger answer. :)

edited May 23, 2017 at 11:58

CommunityBot

11 silver badge

answered May 5, 2015 at 3:13

abarnert

368k54 gold badges626 silver badges691 bronze badges

2 Comments

conjenks Over a year ago

Thank you, I didn't know that the while condition doesn't get checked at the end of every for loop iteration. "Local vs. global" always gets me. The break solved everything. Much appreciated.

abarnert Over a year ago

@conjenks: Right, it only gets checked after the whole for loop is done. while can't "reach into" the code inside its block and break out as soon as its condition becomes false, it just checks the condition, runs the whole block, and repeats.

Collectives™ on Stack Overflow

Python while loop won't exit (Beginner)

2 Answers 2

5 Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

5 Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related