Project Euler task #10 Python wrong answer

Question

The task Project Euler #10 is: The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17. Find the sum of all the primes below two million.

I'm confused by why is my code giving me a wrong answer of 1000000000001. Here it is:

def prime(a):
    for i in range(2,a):
        if a % i == 0:
            return False
            break
        return True

sum = 2
for n in range(3,2000000,2):
    if prime(n):
        sum += n
print(sum)

Could someone explain me what is exactly wrong with it?

Your `prime` method is incorrect. It will return `True` for any number not divisible by `2`. It never reaches the second iteration of the loop. — shriakhilc, Jun 13 '19 at 08:07
The task is to find the sum of all the primes below two million — techyyy, Jun 13 '19 at 08:08
Quick efficiency point - you only need to check divisors up to the square root of a number to test for being prime. — Andrew Allen, Jun 13 '19 at 08:10

knh190 · Answer 1 · 2019-06-13T09:16:48.887

3

You returned too early from the for loop:

def prime(a):
    if a < 2:
        return False
    if a == 2:
        return True
    for i in range(2,a):
        if a % i == 0:
            return False
    # should be after checking all numbers
    return True # this line

Besides you only need to check up to sqrt(a) and exclude even numbers.

import math

# skip even numbers
def prime(a):
    if a == 2:
        return True
    if a % 2 == 0:
        return False
    n = math.ceil(math.sqrt(a))
    for i in range(3, n+1, 2):
        if a % i == 0:
            return False
    return True

edited Jun 13 '19 at 09:16

answered Jun 13 '19 at 08:08

knh190

2,744
1
16
30

this is giving wrong solution `k = sum([i for i in range(2,2000000) if prime(i)])+2` – sahasrara62 Jun 13 '19 at 09:10
@prashantrana which function? I fixed the second one. – knh190 Jun 13 '19 at 09:15
i used the earlier second one, now the solution is right – sahasrara62 Jun 13 '19 at 09:30

score 0 · Answer 2 · answered Jun 13 '19 at 09:06

copying @MrHIDEn solution from here

def get_primes(n):
  m = n+1
  numbers = [True] * m 
  for i in range(2, int(n**0.5 + 1)):
    if numbers[i]:
      for j in range(i*i, m, i):
        numbers[j] = False
  primes = []
  for i in range(2, m):
    if numbers[i]:
      primes.append(i)
  return primes


primes = get_primes(2000000)
print(sum(primes))

output

142913828922

reference: Sieve_of_Eratosthenes this algorithm is faster

Project Euler task #10 Python wrong answer

2 Answers2