Prime Number Finder in Python

Question

I am creating a simple program that will do three things: add up the prime numbers found within the range set by the user, print out the entire list of prime numbers, and print how many prime numbers were found.

# Starting number
lower = int(input("Enter lower range: "))
# Final number
upper = int(input("Enter upper range: "))
print "Running..."
# Variables to keep track of progress
total = 0
list_of_primes = []

# Loop to see whether the number is prime or not
for num in range(lower, upper + 1):
    if num > 1:
        for i in range(2, num):
            if (num % i) == 0:
                break
        else:
            total += num
            list_of_primes.append(num)
    if num == 2:
        total += num
        list_of_primes.append(num)

# Print out the results
print "Finished..."
print "Sum of prime numbers:", total
print "List of prime numbers:", list_of_primes
print "Number of prime numbers:", len(list_of_primes)

The time waiting can be very long, especially with large numbers (max is around 3,000,000,000). Is there any way to shorten the time needed to run the program (thus improve efficiency) and make the code more elegant and readable?

Note: Negative numbers will work. No errors will be thrown.

EDIT: I have added three more lines of code, which helps to reduce time spent by removing all even numbers immediately except 2, which actually is prime.

Answer 1

Your coding style is clean enough, although you could add longer more descriptive names, and use functions instead of doing everything at the top level. However your main issues are related to choice of algorithm for finding the prime numbers.

Your algorithm is currently to test whether it is dividable by all numbers below it self. And this you repeat for each new number. This is by far the most ineffective algorithm for finding primes, so here are some basic stuff to do better algorithms:

• No need to check even numbers – Your loop could skip every even number since the division by 2 should eliminate all other even numbers...
• No need to check beyond square root of \$n\$ – If none of the numbers below the square root divides it, then none above will divide it either. This makes sense as if it's not prime you'll have that \$a*b = n\$, and if \$a\$ is larger than the square root, \$b\$ has to be lower.
• Avoid multiplies of 3's (as well as 2's) – Another optimization of the brute force is to change the incrementation from 2, as in the sequence: 5, 7, 9, 11, 13, 15, 17, 19, 21, ... One can see that to avoid the 3's (in bold) one adds +2, +4, +2, +4. This can be simplified to an initial value of increment = 2 and then let increment = 6 - increment.
• Keep track of earlier primes – Finally, still using a naive approach, you should keep track of earlier primes, as for lower values testing for division against non-primes is also a waste of time.

However you should probably look into more efficient algorithms (see Wikipedia's Generating primes. One good candidate is the Sieve of Erasthones, i.e. like in this answer which has a cool animation as well.

Answer 2

Disclaimer: I'm not a Python expert

Bug

As is, your code has a bug.

Enter lower range: 2   
Enter upper range: 10
Running...
Finished...
Sum of prime numbers: 19
List of prime numbers: [2, 2, 3, 5, 7]
Number of prime numbers: 5

To fix this bug, change

if num == 2:

to

elif num == 2:

Also, it's not really a bug, but this takes a really, really long time to run for max = 3,000,000,000. I can't get it to finish even 1/1000 of that...

Other Stuff

Include a shebang line to clarify how you want your code to be interpreted (which environment).

Your variable names are descriptive. There's no need to comment things that repeat the variable names.

Your algorithm is sort of slow. The classic Sieve of Eratosthenes is probably your best bet. Be careful how you implement it -- you can spend a lot of time re-testing values.

Result

After making the changes, this is what I ended up with

#!/usr/bin/env python

lower = int(input("Enter lower range: "))
upper = int(input("Enter upper range: "))

print "Running..."

sieve = list(range(upper + 1))
length = len(sieve)

# Keeping track of the primes will save time later

primes = []


current = 2
while current < length:
  primes.append(current)
  index = current * 2
  while index < length:
    sieve[index] = 0
    index = index + current
  current = current + 1
  # do not waste time with multiples
  while current < length and not sieve[current]:
    current = current + 1

# enforce the lower bound
while primes[0] < lower:
  primes.pop(0)

print "Finished..."
print "Sum of prime numbers:", sum(primes)
print "List of prime numbers:", primes
print "Number of prime numbers:", len(primes)

This could be improved to only check odd numbers (or only check non-multiples of three, etc.), but I'll leave that for you.

Final note

If you really want to compute primes over 3bn, I wouldn't recommend using Python. I would recommend using a language with less overhead (maybe C?) and caching the first 1000 or so primes. When you run your sieve, print out each new prime as it is found, and just run your program with the biggest max you can fit. The program might not terminate, but you'll get some big primes...

Answer 3

Everything holroy said, about choice of algorithm especially. Also:

1. Skip numbers more quickly: lower = max(lower, 2) before you enter the loop will not only save you the iterations for negative numbers, but will also let you remove the if num > 1 test that's inside the loop, for savings no matter the input.

2. Move as much as possible outside the loop: n == 2 is only going to happen once, so do it beforehand to save an 'inside the loop' operation.

3. You only need to test up to sqrt(num). (but, per above, avoid computing it more than once)

4. When I went to write my own version of this, I found myself replacing your:

   for i in range(2, num):
       if (num % i) == 0:
           break
   else:
       total += num
       list_of_primes.append(num)
   

   with:

   is_prime = not any(num % i == 0 for i in range(2, num))
   if is_prime:
       total += num
       list_of_primes.append(num)
   

So, using both of those, your loop looks like:

list_of_primes = []

# test 2 beforehand for speed
if lower <= 2 <= upper:
    total += 2
    list_of_primes.append(2)

# no sense looking for primes below 3
range_lower = max(lower, 3)

# the largest factor we need to test is sqrt(num)
max_factor = int(num**0.5)

for num in range(range_lower, upper + 1):
    if not any(num % i == 0 for i in range(2, max_factor)):
        total += num
        list_of_primes.append(num)