'Why does it take so long to show the output of problem 10 of Project Euler?
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)
Solution 1:[1]
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
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
| Solution | Source |
|---|---|
| Solution 1 | Kelly Bundy |
