Основное сито/пары в диапазоне

Я пытаюсь написать генератор простого сита, который я преобразовываю в список для печати, а затем печатаю простые числа в заданном диапазоне. Я почти уверен, что мое количество пар правильное, но по какой-то причине я получаю дополнительные значения в моем списке простых чисел, которые не являются простыми. (Я сразу уловил это, потому что мое последнее значение в выводе было 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)

python primes sieve-of-eratosthenes sieve
person greenteam    schedule 08.09.2016    source источник
comment
@ Жан-Франсуа Фабр, да, ты прав, извини за это. Я просто возился с границами, чтобы посмотреть, смогу ли я понять, почему я получаю дополнительные числа. это должно быть н.   -  person greenteam    schedule 08.09.2016

Ответы (1)


arrow_upward
0
arrow_downward

ваша функция сита неверна. Вы отмечаете все числа как не простые, начиная с «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))
person Jean-François Fabre    schedule 08.09.2016
comment
запуск внутреннего цикла из from i * i был бы быстрее - person marcadian; 08.09.2016
comment
это было бы лучше всего сделать :) - person Jean-François Fabre; 08.09.2016
comment
ах. Да, ты прав. Я считаю, что вы можете даже начать с i * i. Как ни странно, это также не исправило вывод. спасибо, что поймали это, хотя. - person greenteam; 08.09.2016
comment
вывод кажется нормальным на небольших образцах, которые я пробовал. Ваш метод подсчета 2 простых чисел с расстоянием 2 работает правильно. Проблема в том, что когда у вас есть 3,5,7, вы получаете 2 пары. Может быть, вы хотели пропустить 5,7, потому что уже принадлежит 3,5? - person Jean-François Fabre; 08.09.2016
comment
Я говорю о собственно функции сита. Когда я напечатал список простых чисел от 1600 до 3600 сотен, я получил все простые числа, но также и некоторые дополнительные числа, которые не являются простыми. - person greenteam; 08.09.2016
comment
Я сомневаюсь в этом, я проверил членов ans по простому тесту, и все они были простыми. - person Jean-François Fabre; 09.09.2016