Prime Sieve/pairs in a range

Question

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

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 < 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 > 1600]

 print ans

 print "pairs:", pairs(ans)

@Jean-FrançoisFabre yeah you're right ,sorry about that. I was just messing with the bounds to see if I could figure out why I was getting some extra numbers. that should be n. — greenteam

Jean-François Fabre Jean-François Fabre · Accepted Answer · 2016-09-08T20:29:56

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 prime*prime

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

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

to test your list, I suggest you add a prime test so you are sure:

# 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))

Prime Sieve/pairs in a range

1 Answers