Why does it take so long to show the output of problem 10 of Project Euler?

user_18372816 0
Viewed 72

I have wrote some code in Python to solve problem 10 of Project Euler: 'Find the sum of all the primes below two million'. My code works, but not optimal. It takes a lot of time to show the output.

When I am trying to do the problem with primes below 20000 it works. When I change it to 200 000 or 2 million, it doesn't show the output and it is just calculating and it takes a lot of time, whereas I expected it to be faster, since the calculations aren't too difficult. I've never had the output. It almost seems like it's an infinite loop. Does anyone know what the problem is?

This is my code:

answer = 0
for number in range (2, 2000000):  
    if number > 1:  
        for i in range (2, number):  
            if number % i == 0:  
                break  
        else:  
            answer += number
print(answer)
primes python
1 Answers

As mentioned in the comments try a faster algorithm such as Sieve of Eratosthenes:

answer = 0
n = 2_000_000
sieve = set()
for x in range(2, n + 1):
    if x not in sieve:
        answer += x
        sieve.update(range(x * x, n + 1, x))
print(answer)

Usage:

$ time python sieve.py
142913828922
python sieve.py  0.34s user 0.03s system 98% cpu 0.376 total

Better version suggested by @Bakuriu:

answer = 0
n = 2_000_000
# Add 2 the only even prime number.
answer += 2
sieve = set()
# Check only odd numbers.
for x in range(3, n + 1, 2):
    if x not in sieve:
        answer += x
        sieve.update(range(x * x, n + 1, 2 * x))
print(answer)

Usage:

$ time python sieve_better.py
142913828922
python sieve_better.py  0.19s user 0.02s system 98% cpu 0.211 total
user_63282560
Related