Storing a prime number generator

Question

I have a python class that generates nth a prime number, starting from the n-1st number and increments. Then it divides all primes that are already in the list to the floor (sqrt (candidate)). But my class just falls into endless loops, 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 the starting value in your main list. Then the increment function searches for numbers that are not divisible by 1 . Since there are no such numbers, he is always looking.

You must start with 2 as the initial smallest prime or add a special register that handles the generation of the first prime.

Answer 2

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

• You do not use self.n and do not need it, because Python lists know their length.
• However, you can use some caching to remember the number of simple checks to avoid complex calculations.
• primelst is ugly as an identifier: except for random vowels like this one is very non-pythonic, including the type name in the identifier name ("list") is contrary to the spirit of duck input. Just specify containers with multiple values.
• Prefer short functions. Extract the primary discovery from the add-to-list logic and the code will be greatly simplified. It is not possible to perform both breaks and returns inside a nested loop.
• You can make the main function "increment" a generator and get access to primes on demand when you create them. :)
• In the standard library, you can use tools that simplify (a) creating unlimited, counted loops and (b) checking each divisor in a range.

In this way:

 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 a matter of language or algorithm, but debugging :). Add four print statements inside your loop (one for each conditional branch), and you will very quickly understand why your program does not seem to end. It’s much better to understand what comes of you through research (to teach someone to fish, not give them fish ...).

Good luck

Answer 4

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

Here is my modified version - I removed 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

Make 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 incorrect.