Memoization with prime number generator

Question

I have a python class that generates the nth prime number by starting at the n-1th prime and increments. Then divides by all the primes already in the list up to floor(sqrt(candidate)). But my class just gets into an infinite loops somewhere and I can't figure out why.

class prime_list():
    def __init__(self):
        self.primelst = [1]
        self.n = 1

    def increment(self):
        self.n+=1
        candidate = self.primelst[-1]+1
        limit = int(math.floor(math.sqrt(candidate)))
        prime = True
        while True:
            for p in self.primelst:
                if p>limit:
                    break
                if (candidate % p) == 0:
                    prime = False
                    break
            if prime:
                self.primelst.append(candidate)
                return
            else:
                candidate += 1
                limit = int(math.floor(math.sqrt(candidate)))
                prime = True

if __name__=="__main__":
    p = prime_list():
    p.increment()

Answer 1

The problem is that you put 1 as a starting value in your prime list. The increment function then searches for numbers not divisible by 1. Since there are no such numbers, it searches forever.

You should start with 2 as the initial smallest prime number or add a special case handling the generation of the first prime.

Answer 2

Some notes, in addition to the fix described by others:

• You don't use self.n and won't need it, since Python lists know their length.
• You could, however, use some caching to remember the number of primes to check, to avoid a complex calculation.
• primelst is ugly as an identifier: leaving out random vowels like that is highly un-Pythonic, and including a type name in the identifier name ("list") is counter to the spirit of duck-typing. Just name containers with plurals.
• Prefer short functions. Factor out the prime detection from the add-to-list logic, and the code becomes greatly simplified. Having both breaks and returns inside a nested loop is difficult to follow.
• You could make the main 'increment' function a generator, and get access to the primes on-demand while they're being generated. :)
• There are tools in the standard library you can use to simplify (a) making unbounded, counted loops and (b) checking every divisor in a range.

Thus:

class prime_list():
    def __init__(self):
        self.primes = [2]
        self.to_use = 1


    def test(self, candidate):
        # Check if we need to expand the list of used primes.
        # Written a bit paranoid-ly
        while len(self.primes) > self.to_use:
            next = self.primes[self.to_use]
            # Note the mathematical rearrangement. :)
            if candidate <= next * next: self.to_use += 1
        # Test all the primes <= sqrt(candidate).
        return all(candidate % p != 0 for p in self.primes[:self.to_use])


    def __iter__(self):
        import itertools
        for candidate in itertools.count(3):
            if self.test(candidate):
                self.primes.append(candidate)
                yield candidate


if __name__ == "__main__":
    my_primes = prime_list()
    for p in my_primes:
        print "Generated:", p
        if p > 1000000: break
    print "Number of primes generated:", len(my_primes.primes)