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)

Answer 3

This is not exactly a language or algorithm question, but a debugging one :). Add four print statements inside your loop (one at each conditional branch) and you'll very quickly see why your program doesn't seem to end. It's far better to figure out what's happening by yourself through investigation (teach someone to fish instead of giving them a fish...).

Good luck!

Answer 4

Karl Knechtel's answer is correct, but sluggish; the problem is that to_use is advanced too far and too soon.

Here is my amended version - I have stripped the comments.

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


def test(self, candidate):
    next = self.primes[self.to_use]
    if candidate >= next * next:
      self.to_use += 1
      print candidate, next
    return all(candidate % p != 0 for p in self.primes[:self.to_use])


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


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

Answer 5

Let's do a run:

// self.primelst = [1]
// self.n = 1

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

So the while loop repeats endlessly. The algorithm is wrong.