Prime number generator in Python

Question

I have made a Python program that can perform some prime number functions. For example, it can produce an endless output of sequential primes. I am looking for ways to make it faster and cleaner. When I was making it, I had a huge amount of trouble using generators, I don't know why, and what the problems were, because I made it long ago, so I had to stick to for loops and class variables in the end.

class Maths():
    prime = [2]
    squares = []
    primenum = 3
    sqrnum = 1
    fermat_number_true = 0
    fermat_number_false = 1

    def prime_generator(self):
        while True:
            if self.is_prime(self.primenum):
                self.prime.append(self.primenum)
                self.primenum += 2
                return self.primenum - 2
            self.primenum += 2

    def is_prime(self, num):
        for divisor in self.prime:
            quotient = num / divisor
            if quotient == int(quotient):
                return False
        return True

    def square_generator(self):
        while True:
            self.sqrnum += 1
            return (self.sqrnum - 1) * (self.sqrnum - 1)

    def square_output(self):
        while True:
            print(self.square_generator())

    def prime_output(self):
        while True:
            print(self.prime_generator())

    def prime_on_enter(self):
        while True:
            input()
            print(self.next_prime())

    def square_on_enter(self):
        while True:
            input()
            print(self.next_square())

    def next_prime(self):
        return self.prime_generator()

    def next_square(self):
        return self.square_generator()

    def next_fermat(self):
        while True:
            prime = self.next_prime()
            try:
                while self.squares[-1] < prime:
                    self.squares.append(self.next_square())
            except IndexError: self.squares.append(self.next_square())
            if self.isfermat_alg2(prime):
                self.fermat_number_true += 1
                return True, prime
            else:
                self.fermat_number_false += 1
                return False, prime
    def next_fermatf(self):
        true, num = self.next_fermat()
        if true:
            print("%d\t\t%f" % (num, (self.fermat_number_true / (self.fermat_number_false + self.fermat_number_true)) * 100))
        else:
            print("%d\tX\t%f" % (num, (self.fermat_number_true / (self.fermat_number_false + self.fermat_number_true)) * 100))

    def fermat(self):
        while True: self.next_fermatf()

    def isfermat_alg1(self, num, squares):
        for square in squares:
            if num > square:
                difference = num - square
                if difference in squares:
                    return True
        else:
            return False

    def isfermat_alg2(self, num):
        return bool(num % 4 == 1)

def main(): mathsobj.prime_output()

mathsobj = Maths()

if __name__ == '__main__':
    main()

Answer 1

A few quick notes:

In case of square_generator() and next_fermat() you have unnecessary...

while True:

Anytime all paths through the loop encounter a return or break, the loop will never loop.

This:

 return bool(num % 4 == 1)

can be:

 return num % 4 == 1

since the == will always produce a bool.

I would code:

def next_fermatf(self):
    true, num = self.next_fermat()
    if true:
        print("%d\t\t%f" % (num, (self.fermat_number_true / (self.fermat_number_false + self.fermat_number_true)) * 100))
    else:
        print("%d\tX\t%f" % (num, (self.fermat_number_true / (self.fermat_number_false + self.fermat_number_true)) * 100))

more like:

def next_fermatf(self):
    is_next_fermat, num = self.next_fermat()

    msg = "" if is_next_fermat else "X"        
    print("%d\t%s\t%.1f%%" % (num, msg, 
        100.0 * self.fermat_number_true /
        (self.fermat_number_false + self.fermat_number_true))))

1. Changing true to is_next_fermat allows if is_next_fermat to be read, while if true reads more awkwardly.
2. Eliminate common code
3. Keep the code below the pep8 recommended 80 columns
4. Format the % with fixed decimal and show the units.

Answer 2

While @StephenRauch has already commented on most of the stylistic issues of your code, I would like to propose some alternative algorithms.

But first, one last stylistic issue. You seem to be using the class basically only to have a namespace. While namespaces are a honking good idea and we should do more of them, this is easier achieved by putting all these functions into a separate file, e.g. prime_utils.py and then do import prime_utils. This way you call these functions like prime_utils.is_prime in your other code. If you don't want that, use from prime_utils import is_prime, primes and call them directly.

---

For the infinite prime number generator, I would use something like this, which I got from a python cookbook site, which I already recommended in an answer to a similar question. Alternative algorithms can be found, for example in this Stack Overflow post.

def primes():
    '''Yields the sequence of prime numbers via the Sieve of Eratosthenes.'''
    D = {}
    yield 2
    # start counting at 3 and increment by 2
    for q in itertools.count(3, 2):
        p = D.pop(q, None)
        if p is None:
            # q not a key in D, so q is prime, therefore, yield it
            yield q
            # mark q squared as not-prime (with q as first-found prime factor)
            D[q*q] = q
        else:
            # let x <- smallest (N*p)+q which wasn't yet known to be composite
            # we just learned x is composite, with p first-found prime factor,
            # since p is the first-found prime factor of q -- find and mark it
            x = p + q
            while x in D or x % 2 == 0:
                x += p
            D[x] = p

This is basically a Sieve of Eratosthenes that infinitely yields prime numbers.

---

I don't quite understand your next_fermat. If you want a generator for the Fermat numbers, I would use either this:

def fermat_numbers():
    yield from (2**2**n + 1 for n in itertools.count())

Or use the recurrence relation \$F_n = (F_{n-1} - 1)^2 +1\$:

def fermat_numbers2():
    F_n = 3
    while True:
        yield F_n
        F_n = (F_n - 1)**2 + 1

If you actually want the Fermat primes, since there is only five known ones in the whole world and they are the first five Fermat numbers, you could hard-code them:

def fermat_primes():
    yield from islice(fermat_numbers(), 5)

or use a/your is_prime function:

def fermat_primes2():
    yield from (n for n in fermat_numbers() if is_prime(n))

---

Incidentally, I would use a different is_prime. Yours has a confusing interface. If I use it stand-alone, before calling any other prime-related functions of your class, m.is_prime(5) returns False, because self.prime == [2].

def is_prime(n):
    """Test for primality by checking divisibility by `6k +- 1`."""
    # easy cases
    if n == 1:
        return False
    if n in [2, 3, 5, 7]:
        return True
    # exclude even numbers and numbers divisible by 3
    if n % 2 == 0 or n % 3 == 0:
        return False
    # only test 6k +- 1 <= sqrt(n)
    for i in -1, 1:
        x = 6 + i
        while x <= math.sqrt(n):
            if n % x == 0:
                return False
            x += 6
    return True

This tests for divisibility by 2 and 3 first and then only tests numbers of the format \$6*k \pm 1\$. This works because all integers can be expressed as \$(6k + i)\$ for some integer k and for i = −1, 0, 1, 2, 3, or 4. 2 divides \$(6k + 0), (6k + 2), (6k + 4)\$. And 3 divides \$(6k + 3)\$. So a more efficient method is to test if n is divisible by 2 or 3, then to check through all the numbers of form \$6k \pm 1 \leq \sqrt{n}\$. This is 3 times as fast as testing all n (see Wikipedia).

---

Lastly, square_numbers could just be:

def square_numbers():
    yield from (n**2 for n in itertools.count())