title: Sieve of Eratosthenes in Python very slow
body: <p>I've written a program in Python that finds all the prime numbers below a given number (<em>n</em>), and sums them up (to answer <strong>Project Euler's Problem 10</strong>). To solve the problem, I need to add up all primes below 2,000,000. My program works, but seems very inefficient (when <em>n</em> = 2,000,000 , it won't show the answer even after 30 minutes). I have found another program that is much and much faster, though I can't seem to find out what makes mine slower than the one I've found. Here are the two programs:</p>
  
  <p><strong>Slow program (the one I've written):</strong></p>
  
  <pre><code>def print_sum(n):
  
      prime_array = {}
      sum = 0
  
      for i in range(2, n+1):
          prime_array[i] = 1
  
      prime_array[0] = 0
      prime_array[1] = 0
  
      for j in range(2, int(math.sqrt(n)) + 1):
          if prime_array[j] == 1:
              for k in range(2, n + 1):
                  prime_array[j*k] = 0
  
      for x in prime_array:
          if prime_array[x] == 1:
              sum = sum + x
  
      print sum
  
  print_sum(2000000)
  </code></pre>
  
  <p><strong>Fast program:</strong></p>
  
  <pre><code>n = 2000000
  prime_array = [True] * n
  sum = 0
  
  def mark(prime_array, x):
      for i in xrange(x+x, len(prime_array), x):
          prime_array[i] = False
  
  
  for x in xrange(2, int(len(prime_array)** .5) + 1):
      if prime_array[x]: mark(prime_array, x)
  
  for y in xrange(2, n):
      if prime_array[y]:
          sum = sum + y
  
  print sum
  </code></pre>
  
  <p>Thanks in advance!</p>