22
\$\begingroup\$

I'm really new to coding so I'm looking for a bit of feedback on this twin prime finder. She works pretty decent but I know it could be better.

import math
primes = []
def get_primes(lower, upper):
  for num in range(lower, upper):
    for i in range(2, num):
      if num % i == 0:
        break
    else:
      primes.append(num)
print get_primes(int(raw_input("Enter lower boundary")), int(raw_input("Enter upper boundary")))
print primes

for i in range(0, len(primes) - 1):
  if primes[i+1] - primes[i] == 2:
    print str(primes[i]), str(primes[i+1]) 
\$\endgroup\$
  • 1
    \$\begingroup\$ Recommended reading: Sieve of Eratosthenes \$\endgroup\$ – user31517 Feb 7 '17 at 19:14
25
\$\begingroup\$

Style

The Style Guide for Python Code called PEP 8 recommends a 4-space indent.

More functions

You could split your logic into smaller logical pieces which are easier to understand, to test and to optimise (I'll come back to this later).

For instance:

def is_prime(n):
    for i in range(2, n): 
        if n % i == 0:
            return False
    return True

def get_primes(lower, upper):
    for num in range(lower, upper):
        if is_prime(num):
            primes.append(num)

Avoid global

Your function get_primes would be much easier to use if instead of appending to a global variable, it was using a proper return value.

def get_primes(lower, upper):
    primes = []
    for num in range(lower, upper):
        if is_prime(num):
            primes.append(num)
    return primes

primes = get_primes(5, 56)  # get_primes(500000, 560000)
print primes

More functions (again)

You could add a function get_twin_primes to return ... the twin primes.

if __name__ == "__main__":

It is practical (and conventional) in Python to use the if __name__ == "__main__": to separate your functions/classes definitions from the code actually using it. This makes code reuse possible via import : the functions/classes can be used by other modules without triggering all your computations.

Now, the whole code looks like:

import math

def is_prime(n):
    for i in range(2, n):
        if n % i == 0:
            return False
    return True

def get_primes(lower, upper):
    primes = []
    for num in range(lower, upper):
        if is_prime(num):
            primes.append(num)
    return primes

def get_twin_primes(primes):
    twins = []
    for i in range(0, len(primes) - 1):
        if primes[i+1] - primes[i] == 2:
            twins.append((primes[i], primes[i+1]))
    return twins

if __name__ == "__main__":
    primes = get_primes(5, 56)  # get_primes(500000, 560000)
    print primes
    for a, b in get_twin_primes(primes):
        print a, b

More beautiful loop

I highly recommend Ned Batchelder's excellent talk called "Loop Like A Native" (and any other talk he's done). You'll learn a lot about iterations in Python and that basically, anytime you write "range(len(list))", there is a better way.

In your case, you'll find various ways to iterate over consecutive items in a list like this:

def get_twin_primes(primes):
    twins = []
    for p1, p2 in zip(primes, primes[1:]):
        if p2 - p1 == 2:
            twins.append((p1, p2))
    return twins

(In Python 2, you could use itertools.izip instead of zip but if you're learning Python, you should try to use Python 3 directly).

Then, this can easily be rewritten using a list comprehension:

def get_twin_primes(primes):
    return [(p1, p2) for p1, p2 in zip(primes, primes[1:]) if p2 - p1 == 2]

More list comprehensions

You can also use list comprehensions in get_primes:

def get_primes(lower, upper):
    return [num for num in range(lower, upper) if is_prime(num)]

Using builtins (and generator expressions)

Your function could be writen in a more concise way using the builtin all.

def is_prime(n):
    return all(n % i != 0 for i in range(2, n))

You can easily read this as "a number is prime is all divisions have a non-zero remainder".

It's exactly like the logic you had before but you are reusing already existing builtins and it teaches you new things :)

Now, the whole code looks like:

import math

def is_prime(n):
    return all(n % i != 0 for i in range(2, n))

def get_primes(lower, upper):
    return [num for num in range(lower, upper) if is_prime(num)]

def get_twin_primes(primes):
    return [(p1, p2) for p1, p2 in zip(primes, primes[1:]) if p2 - p1 == 2]

if __name__ == "__main__":
    primes = get_primes(5, 56)  # get_primes(500000, 560000)
    print primes
    for a, b in get_twin_primes(primes):
        print a, b

Optimisation

A simple yet very efficient optimisation when checking for prime is to use the fact that if a number is composite, for any pair of factors, one is less than or equal to the square root, and the other is greater than or equal to the square root, so you don't need to check the values larger than the square root of the number you are considering. There you can write something like:

def is_prime(n):
    """Checks if a number is prime."""
    if n < 2:
        return False
    return all(n % i for i in range(2, int(math.sqrt(n)) + 1))

Another optimisation you could do is to use the step argument of range in get_primes to iterate over odd numbers only (and add "2" at the beginning if needed).

\$\endgroup\$
  • 1
    \$\begingroup\$ This is a great answer. For OP, everything before More beautiful loop is stuff that you can read, absorb, and use now. Everything after that is really good advice, but it may take longer to "sink in" (so don't be discouraged if it doesn't all make sense immediately). \$\endgroup\$ – brian_o Feb 7 '17 at 19:02
  • 1
    \$\begingroup\$ Great answer, just to nitpick you probably meant itertools.izip to be used on Python 2. \$\endgroup\$ – niemmi Feb 8 '17 at 7:43
  • 1
    \$\begingroup\$ I think your characterization of "no divisor will be bigger than the square root" is misleading, strictly. Consider 12; one of its factors is 6, which is larger than the square root of 12. It is more "if a number is composite, for any pair of factors, one is less than or equal to the square root, and the other is greater than or equal to the square root, so you don't need to check the values larger than the square root". Or along those lines, anyway. The net result is the same; stop testing when you exceed the square root. You could also only test odd numbers from 3 upwards. \$\endgroup\$ – Jonathan Leffler Feb 8 '17 at 14:58
  • \$\begingroup\$ @niemmi This is correct. I've updated my answer. Thanks for spotting this. \$\endgroup\$ – SylvainD Feb 8 '17 at 15:01
  • \$\begingroup\$ @JonathanLeffler This is correct. I've updated my answer. Thanks for spotting this. \$\endgroup\$ – SylvainD Feb 8 '17 at 15:01
12
\$\begingroup\$

To continue from Josay's answer, there is a better way to generate primes below a limit. This is a prime sieve, of which the easiest one is the Sieve of Eratosthenes.

You can even write it as a generator in Python, like so:

def prime_sieve(limit):
    # Array denoting if the index is prime, initially assume all primes
    prime = [True] * limit
    # Set the starting conditions
    prime[0] = prime[1] = False

    for i, is_prime in enumerate(prime):
        # No number smaller than i marked i as a multiple of it
        if is_prime:
            yield i
            # Set all multiples of i as not prime, starting with i*i
            for n in xrange(i * i, limit, i):
                prime[n] = False

Note that you need to replace xrange with range, if you are using Python 3.x.

Now that it is a generator, looping over it two at a time with zip, like Josay did, is slightly wasteful (we would need two generators, each with its almost identical internal state being saved, so taking twice the memory...), even though it is perfectly good if they are lists. It is easier to just save the previous state in a variable, like so:

def prime_pairs(lower, upper):
    # Initialize generator of primes up to upper
    primes = prime_sieve(upper)

    # Forward generator up to lower
    p1 = next(primes)
    while p1 < lower:
        p1 = next(primes)

    # Yield all twin primes
    for p2 in primes:
        if p2 - p1 == 2:
            yield p1, p2
        p1 = p2


if __name__ == "__main__":
    lower = int(raw_input("Enter lower limit: "))
    upper = int(raw_input("Enter upper limit: "))
    for pair in prime_pairs(lower, upper):
        print pair

Replace print pair with print(pair) and raw_input with input in Python 3.x.


The advantage of the prime sieve approach becomes apparent when you need a lot of primes. Using the get_primes function as defined by Josay results for example in:

In[23]: %timeit sum(get_primes(0, 100000))
1 loop, best of 3: 344 ms per loop

Whereas the prime sieve is significantly faster (by about a factor of 25):

In [24]: %timeit sum(prime_sieve(100000))
10 loops, best of 3: 13.9 ms per loop

It is also faster for the task at hand (which is completely dominated by the generating of the primes):

In [33]: %timeit get_twin_primes(get_primes(0, 100000))
1 loop, best of 3: 348 ms per loop

In [34]: %timeit list(prime_pairs(0, 100000))
100 loops, best of 3: 14.5 ms per loop

Another case edge case for this is where the primes you want are all big, but you don't care about the small prime twins. Here Josay's approach wins (because the generator approach will always go through the whole generator, forwarding it to the lower bound):

In [74]: %timeit get_twin_primes(get_primes(99900, 100000))
1000 loops, best of 3: 450 µs per loop

In [75]: %timeit list(prime_pairs(99900, 100000))
100 loops, best of 3: 14.7 ms per loop

99900 was chosen as the lower bound here, so that the range actually contains one prime twin.


And to show how good already Josay's approach was, compared to yours, here is your code (wrapped in a simple function and replacing the print with a yield):

def get_primes_op(lower, upper):
    primes = []
    for num in range(lower, upper):
        for i in range(2, num):
            if num % i == 0:
                break
        else:
            primes.append(num)
    return primes


def twin_primes(primes):
    for i in range(0, len(primes) - 1):
        if primes[i + 1] - primes[i] == 2:
            yield str(primes[i]), str(primes[i + 1])

In [54]: %timeit list(twin_primes(get_primes_op(0, 100000)))
1 loop, best of 3: 1min 38s per loop

In [77]: %timeit list(twin_primes(get_primes_op(99900, 100000)))
1 loop, best of 3: 252 ms per loop

This is a whooping 280 times speed increase from your code to Josay's and a >6500 times speed increase when using my code for the large list of primes, and a 560 times speed increase for Josay and a measly 17 times speed increase for my code in the case of a lower bound close to the upper bound, with the upper bound also being large.

So, as a conclusion, choose the right tool for the job. And test which tool actually is the right tool for your specific needs.

If you need a long list of primes below some upper bound but with a low lower bound (possibly even 0), a prime sieve generator is the way to go.

If you need a list of primes with an arbitrary lower and upper bound, implementing an explicit is_prime function will be faster.

\$\endgroup\$
  • 1
    \$\begingroup\$ As a quick note : the sieve approach may be slower if the lower value gets very big compared to the actual size of the range one wants to check. \$\endgroup\$ – SylvainD Feb 7 '17 at 16:50
  • \$\begingroup\$ Nice! (Unfortunately, I can't update your answer a second time ;-)) \$\endgroup\$ – SylvainD Feb 7 '17 at 17:06
  • \$\begingroup\$ @Josay That's alright, since the question made HNQ some time ago, the upvotes have been coming in steadily :) \$\endgroup\$ – Graipher Feb 7 '17 at 17:07
  • \$\begingroup\$ prime = [True] * limit Uhh, this seems inefficient. Why not use a set (if Python has them)? Searching is O(1), like this approach, but space is O(pi(n)), not O(n). \$\endgroup\$ – Fund Monica's Lawsuit Feb 8 '17 at 4:53
  • \$\begingroup\$ @QPaysTaxes Yes, there are sets in Python and implementations of the sieve with it. The last time I tried one, it ended up being slower than this implementation. The space saving would be nice, but only becomes a problem for limit very large (>1,000,000,000 or so). \$\endgroup\$ – Graipher Feb 8 '17 at 7:41

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.