10

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
dasdachs
  • 709
  • 10
  • 18
  • 1
    You could take a look at this question: http://stackoverflow.com/questions/567222/simple-prime-generator-in-python – ashwinjv Apr 23 '15 at 02:39
  • Does this work if the number is 9? What is the purpose of the counter variable? PS: `a = a + 1` can be simplified to `a += 1` – pygeek Apr 23 '15 at 02:42
  • 1
    Especially the Sieve of Erastothenes implementation in the accepted answer (http://stackoverflow.com/a/568618/3646530). It does involve using generators. You can get more info on what is a generator here: http://stackoverflow.com/a/231855/3646530 – ashwinjv Apr 23 '15 at 02:45
  • look yhis question too: [to-find-first-n-prime-numbers-in-python](http://stackoverflow.com/questions/1628949/to-find-first-n-prime-numbers-in-python) and [find-sum-of-first-1000-prime-numbers-in-python](http://stackoverflow.com/questions/29617690/find-sum-of-first-1000-prime-numbers-in-python/29622071#29622071) – Jose Ricardo Bustos M. Apr 23 '15 at 02:45
  • 1
    You could use a generator algorithm instead of returning a list. You would save memory that way. Also, the preferred algorithm to generate primes less than a number is the sieve of Erastothenes. – Jayanth Koushik Apr 23 '15 at 02:45
  • IMO you can learn a lot if you go through all steps of this: https://stackoverflow.com/a/51133570/512225 – jimifiki Jul 02 '18 at 16:06

10 Answers10

4

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
Community
  • 1
  • 1
James Mills
  • 18,669
  • 3
  • 49
  • 62
  • 1
    for the test it's better to check 2 explicitly and then iterate on `xrange(3, int(x ** 0.5 + 1), 2)`. No point checking all the even numbers. – wim Apr 23 '15 at 03:14
2

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
Community
  • 1
  • 1
nisargap
  • 25
  • 3
1

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!

jimifiki
  • 5,377
  • 2
  • 34
  • 60
  • There are other approaches to calculate the first n primes. I tried to show how to refactor your code. Notice that xrange is faster than xrange for Python 2.x but I'm assuming that you are using 3.x – jimifiki Jul 02 '18 at 16:10
  • On my machine, when n = 100 mine is twice times faster than the original version. When n = 1000 mine is 10 times faster. For n = 10'000 my version is 60 times faster. For n = 100'000 it is 325 times faster! – jimifiki Jul 02 '18 at 16:31
  • 1
    if you check ```a % i == 0``` before ```i >= sqrta``` , the code runs even faster. At least on my laptop, for n = 1,000,000, the code consistently took 5% lesser time. – gouravkr Mar 08 '20 at 04:46
  • @gourevkr thanks for checking. I am considering refactoring the code. – jimifiki Mar 10 '20 at 08:00
  • I was here for schooling and got schooled :-D By the way, on my hardware, we got a program 7 times faster than the accepted answer! – jimifiki Mar 10 '20 at 08:17
1

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,
Vlad Bezden
  • 83,883
  • 25
  • 248
  • 179
1

I made improvements on the solution proposed my jimifiki

import math #for finding the sqare root of the candidate number
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
  c = 5 #candidate number, starting at five
  while c < n: #upper bound, largest candidate will be this or 1 bigger
    p = True #notes the possibility of c to be prime
    c += 2 #increase candidate by 2, avoiding all even numbers
    for a in test: #for each item in test
        if c % a == 0: #check if candidate is divisible
            p = False #since divisible cannot be prime
            break #since divisible no need to continue checking
    if p: #true only if not divisible
        if found[0] > math.sqrt(c): #is samallest in found > sqrt of c
            found.append(c) #if so c is a prime, add it to the list
        else: #if not, it's equal and we need to start checking for it
            test.append(found.pop(0)) #move pos 0 of found to last in test
  return([2] + test + found) #after reaching limit returns 2 and both lists

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 test list only contains numbers smaller than the square root. This is because we add the next number only when we get to the first non-prime not divisible by any of the numbers in test. This number is always the square of the next biggest prime which is also the smallest number in found. The use of the boolean "p" feels kind of spaghetty to me so there might be room for improvement.

Samuel Äijälä
  • 11
  • 2
0

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.

pzp
  • 6,249
  • 1
  • 26
  • 38
0

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)
brian tse
  • 147
  • 2
  • 6
0

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])
dawg
  • 98,345
  • 23
  • 131
  • 206
0

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
SUSHMA SURESH
  • 1
  • 2
0

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}
the-elect
  • 1