Prime Sieve/pairs in a range
<p>I am trying to write a prime sieve generator that I convert to a list for printing and then print the primes in a given range. I'm pretty sure my number of pairs is correct but for some reason I am getting some extra values in my list of primes that aren't prime. (I caught this right away because my last value in the output was 3599 which is not prime).
I'm not really sure if I have some kind of logical error so any help would be awesome</p>

<pre><code>def sieve(n):
     a = [True] * (n)
     a[0] = a[1] = False
     for (i, isPrime) in enumerate(a):
         if isPrime:
              yield i
             for n in range(i*i, n, i):
                 a[n] = False


 def pairs(li):
     pair = 0
     for i, x in enumerate(li):
         if i &lt; len(li)-1:
             if li[i] + 2 == li[i+1]:
                 pair += 1
     return pair

 p_3600 = list(sieve(3600))

 ans = [vals for vals in p_3600 if vals &gt; 1600]

 print ans

 print "pairs:", pairs(ans)
</code></pre>

<p>your sieve function is incorrect. You mark all numbers as not prime, starting by "2".
You need to start by the next multiple of the prime which is <code>prime*prime</code></p>

<p>Hence, you have to start at <code>i*i</code> not <code>i</code> (I used <code>i*2</code> which works but is redundant because already covered by the first loop when <code>i==2</code>)</p>

<pre><code>def sieve(n):
    a = [True] * n
    a[0] = a[1] = False
    for (i, isPrime) in enumerate(a):
     if isPrime:
        yield i
        for j in range(i*i, n, i):
            a[j] = False
</code></pre>

<p>to test your list, I suggest you add a prime test so you are sure:</p>

<pre><code># make sure it works: time-costly but reassuring
import math
for i in ans:
    si = int(math.sqrt(i))+1
    for j in range(2,si):
        if i%j==0:
            raise Exception("%d is not prime (%d)" % (i,j))
</code></pre>

python primes sieve-of-eratosthenes sieve