Basic prime number generator in Python

Question

Just wanted some feedback on my prime number generator. e.g. is it ok, does it use to much resources etc. It uses no libraries, it's fairly simple, and it is a reflection of my current state of programming skills, so don't hold back as I want to learn.

def prime_gen(n):

    primes = [2]
    a = 2 

    while a < n:

        counter = 0 

        for i in primes:
            if a % i == 0:
                counter += 1

        if counter == 0:
            primes.append(a)
        else:
            counter = 0

        a = a + 1

    print primes

Answer 1

I made improvements on the solution proposed my jimifiki

import math
def primes(n):
  test = [3] #list of primes new candidates are tested against
  found = [5] #list of found primes, which are not being tested against
  for c in range(7, n+1, 2): #checking every odd number starting from 7, including n
    for x in test:
      if c % x == 0:
        break #since divisible no need to continue checking
    else:
      if found[0] == math.sqrt(c): #if candidate is equal to square of smallest number not tested against it was a false positive and we need to start testing for said number
        test.append(found.pop(0))
      else: 
        found.append(c)
  return([2] + test + found)

The biggest improvement is not checking for even numbers and checking the square root only if the number is not divisible, the latter really adds up when numbers get bigger. The reason we don't need to check for the square root is, that the first non-prime not divisible by any of the primes in test is always the square of the next biggest prime after the last element of test, which is also the smallest number in found.

Answer 2

You can use Python yield statement to generate one item at the time. Son instead of get all items at once you will iterate over generator and get one item at the time. This minimizes your resources.

Here an example:

from math import sqrt
from typing import Generator


def gen(num: int) -> Generator[int, None, None]:
    if 2 <= num:
        yield 2
    yield from (
        i
        for i in range(3, num + 1, 2)
        if all(i % x != 0 for x in range(3, int(sqrt(i) + 1)))
    )


for x in gen(100):
    print(x, end=", ")

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, 

Answer 3

You start from this:

def prime_gen(n):
    primes = [2]
    a = 2 

   while a < n:
       counter = 0 

       for i in primes:
          if a % i == 0:
              counter += 1

        if counter == 0:
            primes.append(a)
        else:
            counter = 0

        a = a + 1

    print primes

do you really need the else branch? No.

def prime_gen(n):
    primes = [2]
    a = 2 

   while a < n:
       counter = 0 

       for i in primes:
          if a % i == 0:
              counter += 1

        if counter == 0:
            primes.append(a)

        a = a + 1

    print primes

Do you need the counter? No!

def prime_gen(n):
    primes = [2]
    a = 2 

   while a < n:

       for i in primes:
           if a % i == 0:
               primes.append(a)
               break 

        a = a + 1

    print primes

Do you need to check for i larger that sqrt(a)? No.

def prime_gen(n):
    primes = [2]
    a = 3 

   while a < n:
       sqrta = sqrt(a+1)
       for i in primes:
           if i >= sqrta:
               break
           if a % i == 0:
               primes.append(a)
               break 

        a = a + 1

    print primes

Do you really want to manually increase a?

def prime_gen(n):
    primes = [2]

   for a in range(3,n):
       sqrta = sqrt(a+1)
       for i in primes:
           if i >= sqrta:
               break
           if a % i == 0:
               primes.append(a)
               break 

This is some basic refactoring that should automatically flow out of your fingers.

Then you test the refactored code, see that it is buggy and fix it:

def prime_gen(n):
    primes = [2]
    for a in range(3,n):
        sqrta = sqrt(a+1)
        isPrime = True 
        for i in primes:
            if i >= sqrta:
                break
            if a % i == 0:
                isPrime = False
                break 
        if(isPrime): 
            primes.append(a)
    return primes

And finally you get rid of the isPrime flag:

def prime_gen(n):
    primes = [2]
    for a in range(3,n):
        sqrta = sqrt(a+1)
        for i in primes:
            if i >= sqrta:
                primes.append(a)
                break
            if a % i == 0:
                break 
    return primes

now you believe you're done. Then suddenly a friend of yours point out that for a even you are checking i >= sqrta for no reason. (Similarly for a mod 3 == 0 numbers, but then branch-prediction comes in help.) Your friend suggest you to check a % i == 0 before:

def prime_gen(n):
    primes = [2]
    for a in range(3,n):
        sqrta = sqrt(a+1)
        for i in primes:
            if a % i == 0:
                break 
            if i >= sqrta:
                primes.append(a)
                break
    return primes

now you're done and grateful to your brillant friend!

Answer 4

you can do it this way also to get the primes in a dictionary in python

def is_prime(a):
    count = 0
    counts = 0
    k = dict()
    for i in range(2, a - 1):
        k[count] = a % i
        count += 1
    for j in range(len(k)):
        if k[j] == 0:
            counts += 1

    if counts == 0:
        return True
    else:
        return False


def find_prime(f, g):
    prime = dict()
    count = 0
    for i in range(int(f), int(g)):
        if is_prime(i) is True:
            prime[count] = i
            count += 1
    return prime

a = find_prime(20,110)
print(a)

{0: 23, 1: 29, 2: 31, 3: 37, 4: 41, 5: 43, 6: 47, 7: 53, 8: 59, 9: 61, 10: 67, 11: 
71, 12: 73, 13: 79, 14: 83, 15: 89, 16: 97, 17: 101, 18: 103, 19: 107, 20: 109}

Answer 5

To Get the 100th prime number:

import itertools
n=100
x = (i for i in itertools.count(1) if all([i%d for d in xrange(2,i)]))
print list(itertools.islice(x,n-1,n))[0]

To get prime numbers till 100

import itertools
n=100
x = (i for i in xrange(1,n) if all([i%d for d in xrange(2,i)]))
for n in x:
    print n

Answer 6

Being Python, it usually better to return a generator that will return an infinite sequence of primes rather than a list.

ActiveState has a list of older Sieve of Eratosthenes recipes

Here is one of them updated to Python 2.7 using itertools count with a step argument which did not exist when the original recipe was written:

import itertools as it

def sieve():
    """ Generate an infinite sequence of prime numbers.
    """
    yield 2
    D = {}
    for q in it.count(3, 2):   # start at 3 and step by odds
        p = D.pop(q, 0)
        if p:
            x = q + p
            while x in D: x += p
            D[x] = p          # new composite found. Mark that
        else:
            yield q           # q is a new prime since no composite was found
            D[q*q] = 2*q

Since it is a generator, it is much more memory efficient than generating an entire list. Since it locates composite, it is computationally efficient as well.

Run this:

>>> g=sieve()

Then each subsequent call returns the next prime:

>>> next(g)
2
>>> next(g)
3
# etc

You can then get a list between boundaries (i.e., the Xth prime from the first to the X+Y prime...) by using islice:

>>> tgt=0
>>> tgt, list(it.islice(sieve(), tgt, tgt+10))
(0, [2, 3, 5, 7, 11, 13, 17, 19, 23, 29])
>>> tgt=1000000
>>> tgt, list(it.islice(sieve(), tgt, tgt+10))
(1000000, [15485867, 15485917, 15485927, 15485933, 15485941, 15485959, 15485989, 15485993, 15486013, 15486041])

Answer 7

I have some optimizations for the first code which can be used when the argument is negative:

def is_prime(x):    
    if x <=1:
        return False
    else:
        for n in xrange(2, int(x ** 0.5 + 1)):
            if x % n == 0:
                return False
    return True
print is_prime(-3)

Answer 8

Here is the standard method of generating primes adapted from the C# version at: Most Elegant Way to Generate Prime Number

def prime_gen(n):

    primes = [2]

    # start at 3 because 2 is already in the list
    nextPrime = 3

    while nextPrime < n:

        isPrime = True

        i = 0

        # the optimization here is that you're checking from
        # the number in the prime list to the square root of
        # the number you're testing for primality
        squareRoot = int(nextPrime ** .5)

        while primes[i] <= squareRoot:

            if nextPrime % primes[i] == 0:

                isPrime = False

            i += 1

        if isPrime:

            primes.append(nextPrime)

        # only checking for odd numbers so add 2
        nextPrime += 2

    print primes

Answer 9

There are a few optimizations thar are common:

Example:

def prime(x):
    if x in [0, 1]:
        return False
    if x == 2:
        return True
    for n in xrange(3, int(x ** 0.5 + 1)):
        if x % n == 0:
            return False
    return True

• Cover the base cases
• Only iterate up to the square root of n

The above example doesn't generate prime numbers but tests them. You could adapt the same optimizations to your code :)

One of the more efficient algorithms I've found written in Python is found in the following question ans answer (using a sieve):

Simple Prime Generator in Python

My own adaptation of the sieve algorithm:

from itertools import islice


def primes():
    if hasattr(primes, "D"):
        D = primes.D
    else:
        primes.D = D = {}

    def sieve():
        q = 2
        while True:
            if q not in D:
                yield q
                D[q * q] = [q]
            else:
                for p in D[q]:
                    D.setdefault(p + q, []).append(p)
                del D[q]

            q += 1

    return sieve()


print list(islice(primes(), 0, 1000000))

On my hardware I can generate the first million primes pretty quickly (given that this is written in Python):

prologic@daisy
Thu Apr 23 12:58:37 
~/work/euler
$ time python foo.py > primes.txt

real    0m19.664s
user    0m19.453s
sys 0m0.241s

prologic@daisy
Thu Apr 23 12:59:01 
~/work/euler
$ du -h primes.txt
8.9M    primes.txt

Answer 10

Here's a pretty efficient prime number generator that I wrote a while back that uses the Sieve of Eratosthenes:

#!/usr/bin/env python2.7

def primeslt(n):
    """Finds all primes less than n"""

    if n < 3:
        return []

    A = [True] * n
    A[0], A[1] = False, False

    for i in range(2, int(n**0.5)+1):
        if A[i]:
            j = i**2
            while j < n:
                A[j] = False
                j += i

    return [num for num in xrange(n) if A[num]]

def main():
    i = ''
    while not i.isdigit():
        i = raw_input('Find all prime numbers less than... ')
    print primeslt(int(i))

if __name__ == '__main__':
    main()

The Wikipedia article (linked above) explains how it works better than I could, so I'm just going to recommend that you read that.