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).
