Python prime number finder doesn't work (using break command)

Question

I'm trying to make a relatively efficient piece of Python code that will sum all the primes under 2 million, but this code doesn't seem to work. It regards numbers like 9 and 15 prime for some reason:

sum = 2

for num in range(3, 2000000, 2):
  for i in range(2, 1+int(num**0.5)):
    if num % i == 0:
      break
  sum += num

print(sum)

If you want an efficient implementation, you should check out https://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n — SuperStormer, Aug 27 '22 at 22:16

score 2 · Answer 1 · answered Aug 27 '22 at 22:17

As written, your code ignores the checks in the inner for loop, and sums the current number regardless of whether or not it's a prime or not.

Either use a flag variable:

prime_sum = 2

for num in range(3, 2000000, 2):
  is_prime = True
  for i in range(2, 1+int(num**0.5)):
    if num % i == 0:
      is_prime = False
      break
  if is_prime:
    prime_sum += num

print(prime_sum)

or use the for loop's else clause (which only runs after the loop runs to completion - ie. no break):

prime_sum = 2

for num in range(3, 2000000, 2):
  for i in range(2, 1+int(num**0.5)):
    if num % i == 0:
      break
  else:
    prime_sum += num

print(prime_sum)

score 1 · Answer 2 · answered Aug 27 '22 at 22:17

You're not checking whether the inner loop found a factor or not before adding num to sum.

You can use the else: block of a loop to tell whether the loop finished or stopped due to break.

sum = 2

for num in range(3, 2000000, 2):
    for i in range(2, 1+int(num**0.5)):
        if num % i == 0:
            break
    else:
        sum += num

print(sum)

score 1 · Answer 3 · answered Aug 27 '22 at 22:20

You're breaking out of the inner loop if the number is not prime, but then are still executing the line

sum += num

There are multiple solutions to this.

Moving the primality test to a function

def is_prime(x):
    for i in range(2, int(x ** 0.5) + 1):
        if x % i == 0:
            return False
    return True
sum = 2
for num in range(3, 2000000, 2):
    if is_prime(num):
        sum += num
print(sum)

is_prime variable

sum = 2

for num in range(3, 2000000, 2):
  is_prime = True
  for i in range(2, 1+int(num**0.5)):
    if num % i == 0:
      is_prime = False
      break
  if is_prime:
    sum += num

print(sum)

all() and a list comprehension

sum = 2
for num in range(3, 2000000, 2):
    if all([num % i != 0 for i in range(int(x ** 0.5) + 1)]):
        sum += num
print(sum)

Python prime number finder doesn't work (using break command)

3 Answers3