Prime Number Generator (6n + 1 or 6n - 1)

Question

This generator is like most where it brute forces an integer: it see whether the integer is divisible by any of the primes; if so, then it's not a prime and vice versa. This though only compares values 6n + 1 and 6n - 1 starting with n as 1 as all primes larger than 3 can be written as 6n + 1 or 6n - 1 where n is a positive integer.

Examples: 7 is 6(1) + 1 (n = 1) and 17 is 6(3) - 1 (n = 3).

Code:

primes = [2, 3]
limit = 0
n = 1
is_prime = True

while True:
    try:
        limit = int(raw_input("Enter a positive integer larger than 3: "))
    except ValueError:
        print "Please enter a positive integer larger than 3!"
    else:
        if limit <= 3:
            print "Please enter a positive integer larger than 3!"
        else:
            break

while True:
    minus_prime = 6*n - 1
    plus_prime = 6*n + 1

    if minus_prime < limit:
        for x in primes:
            if minus_prime % x == 0:
                is_prime = False
                break
        if is_prime:
            primes.append(minus_prime)
        is_prime = True
    elif minus_prime > limit:
        print primes
        break

    if plus_prime < limit:
        for x in primes:
            if plus_prime % x == 0:
                is_prime = False
                break
        if is_prime:
            primes.append(plus_prime)
        is_prime = True
    elif plus_prime > limit:
        print primes
        break

    n += 1

Basically, given preset primes 2 and 3, find all primes that are less than limit by producing numbers with 6*n + 1 and 6*n - 1 (n increases by one every loop) and checking first if they are over the limit. If so, stop the loop and print out the primes (as a list). If not, brute force through primes to see if the number is prime. If so, add to primes. Else, continue. limit is checked in the first while loop to ensure validity.

I am wondering how to improve the performance of my program, improve its structure, and make it more Pythonic. Try it here

Answer 1

How about:

import math

limit = 100000
primes = [2,3]

def calc_potential_primes(n):
    return [6*n-1, 6*n+1]

def is_prime(x):
    for p in primes:
        if p <= math.sqrt(x):
            if x % p == 0:
                return False
        else:
            break
    return True

n = 1
while True:
    possible_primes = calc_potential_primes(n)
    new_primes = [x for x in possible_primes if is_prime(x) and x < limit]
    primes += new_primes

    if sum(i > limit for i in possible_primes) > 0:
        break
    n += 1

print primes

We don't have to check every prime #, only primes up to sqrt(x).

You run the same code block on 2 different inputs, which can lead to potential bugs where you forget to update variable names as pointed out by Aemyl. If you're going to re-use the same code, it's better to put it into a function to keep the code readable and prevent potential bugs.

Maintaining our code logic inside a function also prevents us from having to update a global variable, which can also lead to additional bugs if at any point we forget to or accidentally update it.

Encapsulating your prime calculations within a function that returns a list of primes will also allow us to make updates to how we generate our primes without having to update the rest of our code. By the same logic, if we want to update how we check if a # is prime (maybe we think of a more efficient solution), we only have to update it in one place, instead of twice in the current case. In this case, functions keep our code maintainable and easy to follow.

By always returning a list, if at any point we want to scale or change how we generate prime number candidates, we can simply update the code logic and return the same object as before (a list) and the rest of our code should work as is. In the current case, we would have to set additional variables, then repeat the prime check code block for each additional variable.

Combining lists with Python's list comprehensions allow us to clearly and easily filter for the items (prime #s) that we want, while maintaining readability and efficiency.

Basically, consider using functions and list comprehensions to keep code readable, simple, maintainable and therefore hopefully as bug-free as possible.

With this I get a timeit of 208 ms ± 682 µs per loop (mean ± std. dev. of 7 runs, 1 loop each) when calculating primes up to 100000

versus 4.28 s ± 52 ms per loop (mean ± std. dev. of 7 runs, 1 loop each) with yours.

Answer 2

Let's first address some of your logic and flow.

One thing that strikes me right away is that you have the same logic written twice, this can be made into a function or, in a more Pythonic fashion can be made into a list comprehension. A for loop is also to be considered for readability.

Moving on, you are using if blocks to check a condition and breaking inside of a while loop that is always true. You can clean this up by changing while True to instead be while plus_prime < limit and minus_prime< limit. It is important to note in this case that you should recompute these values at the end of the loop, so that their current is checked before loop execution rather than after. There are many different approaches to this.

I'm going to specifically break down this part of code:

for x in primes:              #for loops often can instead be comprehensions in python
    if minus_prime % x == 0:  #checking many booleans is also very easy in python
        is_prime = False
        break
if is_prime:
    primes.append(minus_prime)
is_prime = True

because it can be made very elegant in Python.

Instead of having many if statements, a sentinel boolean, and a for loop we can make this very clean with the following:

if all(minux_prime % x for x in primes):
    primes.append(minus_prime)

What is going on here?

The statement minux_prime % x for x in primes is what is called a generator, it is similar to a list comprehension in python but it is different and may not always make a list. Full Discussion here. In this case the generator is being used to make a list

Then we use the Python builtin function all() this function returns a true or false value, True if the passed in list contains no False values. The function all() returns False if there exists any false statement. The Python function any() is the inverse of this, I recommend reading about it as homework ;).

On the topic of efficiency, a sieve is normally the fastest method to work for finding primes. it works by finding early primes, and then removing all values that we know are not primes because of our known primes then iterating.

Here's an implementation