Simple Prime Generator in Python

Question

Hi, 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). Thanks a lot. lincoln.

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

• The continue statement looks wrong.

• You want to start at 2 because 2 is the first prime number.

• You can write "while True:" to get an infinite loop.

Answer 2

This seems homework-y, so I'll give a hint rather than a detailed explanation. Correct me if I've assumed wrong.

You're doing fine as far as bailing out when you see an even divisor.

But you're printing 'count' as soon as you see even one number that doesn't divide into it. 2, for instance, does not divide evenly into 9. But that doesn't make 9 a prime. You might want to keep going until you're sure no number in the range matches.

(as others have replied, a Sieve is a much more efficient way to go... just trying to help you understand why this specific code isn't doing what you want)

Answer 3

your problem is definition of primes

Answer 4

There is a much more efficient, and pretty easy to code, way to do this:

Sieve_of_Eratosthenes

Answer 5

You need to make sure that all possible divisors don't evenly divide the number you're checking. In this case you'll print the number you're checking any time just one of the possible divisors doesn't evenly divide the number.

Also you don't want to use a continue statement because a continue will just cause it to check the next possible divisor when you've already found out that the number is not a prime.

Answer 6

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 Erastothenes, as others have suggested. Here's a nice, optimized implementation with many comments:

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 7

def is_prime(num):
    """Returns True if the number is prime
    else False."""
    if num == 0 or num == 1:
        return False
    for x in range(2, num):
        if num % x == 0:
            return False
    else:
        return True

>> filter(is_prime, range(1, 20))
  [2, 3, 5, 7, 11, 13, 17, 19]

We will get all the prime numbers upto 20 in a list. I could have used Sieve of Eratosthenes but you said you want something very simple. ;)

Answer 8

Here is a good one.

Answer 9

Here is what I have:

def is_prime(num):
    if num < 2:         return False
    elif num < 4:       return True
    elif not num % 2:   return False
    elif num < 9:       return True
    elif not num % 3:   return False
    else:
        for n in range(5, int(math.sqrt(num) + 1), 6):
            if not num % n:
                return False
            elif not num % (n + 2):
                return False

    return True

It's pretty fast for large numbers, as it only checks against already prime numbers for divisors of a number.

Now if you want to generate a list of primes, you can do:

# primes up to 'max'
def primes_max(max):
    yield 2
    for n in range(3, max, 2):
        if is_prime(n):
            yield n

# the first 'count' primes
def primes_count(count):
    counter = 0
    num = 3

    yield 2

    while counter < count:
        if is_prime(num):
            yield num
            counter += 1
        num += 2

using generators here might be desired for efficiency.

And just for reference, instead of saying:

one = 1
while one == 1:
    # do stuff

you can simply say:

while 1:
    #do stuff

Answer 10

You can create a list of primes using list comprehensions in a fairly elegant manner. Taken from here:

>>> noprimes = [j for i in range(2, 8) for j in range(i*2, 50, i)]
>>> primes = [x for x in range(2, 50) if x not in noprimes]
>>> print primes
>>> [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

Answer 11

Here's a simple (Python 2.6.2) solution... which is in-line with the OP's original request (now six-months old); and should be a perfectly acceptable solution in any "programming 101" course... Hence this post.

import math

def isPrime(n):
    for i in range(2, int(math.sqrt(n)+1)):
        if n % i == 0: 
            return False;
    return True;

print 2
for n in range(3, 50):
    if isPrime(n):
        print n

This simple "brute force" method is "fast enough" for numbers upto about about 16,000 on modern PC's (took about 8 seconds on my 2GHz box).

Obviously, this could be done much more efficiently, by not recalculating the primeness of every even number, or every multiple of 3, 5, 7, etc for every single number... See the Sieve of Eratosthenes (see eliben's implementation above), or even the Sieve of Atkin if you're feeling particularly brave and/or crazy.

Caveat Emptor: I'm a python noob. Please don't take anything I say as gospel.

Answer 12

print [x for x in range(2,100) if not [t for t in range(2,x) if not x%t]]