10 problem in the Project Euler is:
The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.
Find the sum of all the primes below two million.
sieve = [True] * 2000000 # Sieve is faster for 2M primes
def mark(sieve, x):
for i in xrange(x+x, len(sieve), x):
sieve[i] = False
for x in xrange(2, int(len(sieve) ** 0.5) + 1):
if sieve[x]: mark(sieve, x)
print sum(i for i in xrange(2, len(sieve)) if sieve[i])
for x in xrange(3, int(n**0.5)+1):
if n % x == 0:
for i in xrange(1,int(2e6),2):
sum += i
Your algorithm is checking every number individually from 2 to N (where N=2000000) for primality.
Snippet-1 uses the sieve of Eratosthenes algorithm, discovered about 2200 years ago. It does not check every number but:
So the algorithm produces all primes up to N.
Notice that it does not do any division, only additions (not even multiplications, and not that it matters with so small numbers but it might with bigger ones). Time complexity is
O(n loglogn) while your algorithm has something near
O(n^(3/2) / logn) as @Daniel Fischer commented), assuming divisions cost the same as multiplications.
From the Wikipedia (linked above) article:
Time complexity in the random access machine model is O(n log log n) operations, a direct consequence of the fact that the prime harmonic series asymptotically approaches
log log n.
n = 2e6 in this case)