title: How to speed up Sieve of Eratosthenes python list generator
body: <p>My problem comes directly from the CS circles site. It's the last problem on the bottom of <a href="http://cscircles.cemc.uwaterloo.ca/18-efficiency/" rel="nofollow noreferrer">this</a> page called 'Primed for Takeoff'. The basic rundown is they want a list of 1,000,001 length, where the index of each item is True if the index is prime, while the index of each item is False if it is not prime. </p>
  
  <p>So, for example, isPrime[13] is True. isPrime[14] is False.</p>
  
  <p>The first little bit of the list 'isPrime' would look like:</p>
  
  <pre><code>isPrime = [False, False, True, True, False, True, False, True, False, False, ...]
  </code></pre>
  
  <p>My problem is the 7-second time limit they have. I have a working code below with a lower number, 101, for debugging purposes. When I bump it up to their required 1,000,001 list length, it takes way too long, I ended up killing the program after a few minutes.
  This is my working (at length 101), very slow code:</p>
  
  <pre><code>n = 101
  c = 2
  isPrime = [False,False]
  for i in range(2,n):
      isPrime.append(i)
  
  def ifInt(isPrime):
      for item in isPrime:
          if type(item) == int:
              return item
  for d in range(2,n):
      if c != None:
          for i in range(c,n,c):
              isPrime[i] = False
          isPrime[c] = True
          c = ifInt(isPrime)
  </code></pre>
  
  <p>Then there's this one I found <a href="https://stackoverflow.com/questions/3939660/sieve-of-eratosthenes-finding-primes-python">here</a>. It has a quicker run time, but only outputs a list of primes, not a list of n length with list[n] returning True for primes and false otherwise. </p>
  
  <p>I'm not sure if this 2nd bit of code really holds the key to creating a prime list of length 1,000,001 in under 7 seconds, but it was the most relevant thing I could find in my research.</p>
  
  <pre><code>def primes_sieve1(limit):
  limitn = limit+1
  primes = dict()
  for i in range(2, limitn): primes[i] = True
  
  for i in primes:
      factors = range(i,limitn, i)
      for f in factors[1:]:
          primes[f] = False
  return [i for i in primes if primes[i]==True]
  
  print primes_sieve1(101)
  </code></pre>
  
  <p>CS circles seems pretty commonly used, but I wasn't able to find a working version of this for Python. Hopefully this will be an easy solve for someone.</p>
  
  <p>This question differs from <a href="https://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n">this one</a> because am not trying to only create a list of primes quickly, but to create a list of all positive integers from 0 to n that are marked as prime by True and non prime by False. </p>