4
\$\begingroup\$

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()
\$\endgroup\$
  • \$\begingroup\$ See this answer for some ideas about speeding up prime number generation. \$\endgroup\$ – Gareth Rees Jan 14 '17 at 19:02
5
\$\begingroup\$

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.
\$\endgroup\$
  • \$\begingroup\$ Thanks, these tips will help tidy up my code. For the while True functions, they are supposed to loop forever, depending on the intended output of the program i. e. it can produce different outputs depending what you put in the final lines. \$\endgroup\$ – user128154 Jan 14 '17 at 20:14
3
\$\begingroup\$

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())
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy