Simple prime number generator in Python

Simple prime number generator in Python

There are some problems:

  • Why do you print out count when it didnt divide by x? It doesnt mean its prime, it means only that this particular x doesnt divide it
  • continue moves to the next loop iteration – but you really want to stop it using break

Heres 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
        if isprime:
            print count
        count += 1

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

# Sieve of Eratosthenes
# Code by David Eppstein, UC Irvine, 28 Feb 2002

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 thats 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 isnt
            # already marked in previous iterations
            yield q
            D[q * q] = [q]
            # q is composite. D[q] is the list of primes that
            # divide it. Since weve reached q, we no longer
            # need it in the map, but well 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.

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)]

[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]

Simple prime number generator in Python

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
        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. 😉

Leave a Reply

Your email address will not be published. Required fields are marked *