Prime Sieve/pairs в диапазоне

Question

Я пытаюсь написать генератор первичного сита, который я конвертирую в список для печати, а затем печатаю простые числа в заданном диапазоне. Я уверен, что число пар правильное, но по некоторым причинам я получаю некоторые дополнительные значения в моем списке простых чисел, которые не являются первичными. (Я сразу понял это, потому что мое последнее значение на выходе было 3599, которое не является простым). Я не совсем уверен, что если у меня есть какое-то логическая ошибка, так что любая помощь будет удивительной

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) 

Answer 1

ваша функция решето неверна. Вы отмечаете все числа как не простые, начиная с «2». Вы должны начать с помощью следующих кратного штриха, который prime*prime

Таким образом, вы должны начать в i*i не i (я использовал i*2, который работает, но является излишним, так как уже охвачено первой петлей, когда 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 

, чтобы проверить свой список, я предлагаю вам добавить простое испытание, так что вы уверены:

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