Simple prime number generator in Python

Question

Could someone please tell me what I'm doing wrong with this code? It is just printing 'count' anyway. I just want a very simple prime generator (nothing fancy).

import math  def main():     count = 3     one = 1     while one == 1:         for x in range(2, int(math.sqrt(count) + 1)):             if count % x == 0:                  continue             if count % x != 0:                 print count          count += 1 

Answer 1

There are some problems:

• Why do you print out count when it didn't divide by x? It doesn't mean it's prime, it means only that this particular x doesn't divide it
• continue moves to the next loop iteration - but you really want to stop it using break

Here's your code with a few fixes, it prints out only primes:

import math  def main():     count = 3          while True:         isprime = True                  for x in range(2, int(math.sqrt(count) + 1)):             if count % x == 0:                  isprime = False                 break                  if isprime:             print count                  count += 1 

For much more efficient prime generation, see the Sieve of Eratosthenes, as others have suggested. Here's a nice, optimized implementation with many comments:

# Sieve of Eratosthenes # Code by David Eppstein, UC Irvine, 28 Feb 2002 # http://code.activestate.com/recipes/117119/  def gen_primes():     """ Generate an infinite sequence of prime numbers.     """     # Maps composites to primes witnessing their compositeness.     # This is memory efficient, as the sieve is not "run forward"     # indefinitely, but only as long as required by the current     # number being tested.     #     D = {}          # The running integer that's checked for primeness     q = 2          while True:         if q not in D:             # q is a new prime.             # Yield it and mark its first multiple that isn't             # already marked in previous iterations             #              yield q             D[q * q] = [q]         else:             # q is composite. D[q] is the list of primes that             # divide it. Since we've reached q, we no longer             # need it in the map, but we'll mark the next              # multiples of its witnesses to prepare for larger             # numbers             #              for p in D[q]:                 D.setdefault(p + q, []).append(p)             del D[q]                  q += 1 

Note that it returns a generator.

Answer 2

re is powerful:

import re   def isprime(n):     return re.compile(r'^1?$|^(11+)\1+$').match('1' * n) is None  print [x for x in range(100) if isprime(x)]  ###########Output############# [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]