Почему моя реализация сита Аткин с видом на номера близко к указанному пределу?

Question

Моя реализация Сито ушки либо упускают простые простуды рядом с пределом или композитами вблизи предела. в то время как некоторые ограничивает работу и другие не. Я полностью запутался как к тому, что не так.

def AtkinSieve (limit):
results = [2,3,5]
sieve = [False]*limit
factor = int(math.sqrt(lim))
for i in range(1,factor):
    for j in range(1, factor):
        n = 4*i**2+j**2
        if (n <= lim) and (n % 12 == 1 or n % 12 == 5):
            sieve[n] = not sieve[n]
        n = 3*i**2+j**2
        if (n <= lim) and (n % 12 == 7):
            sieve[n] = not sieve[n]
        if i>j:
            n = 3*i**2-j**2
            if (n <= lim) and (n % 12 == 11):
                sieve[n] = not sieve[n]
for index in range(5,factor):
    if sieve[index]:
        for jndex in range(index**2, limit, index**2):
            sieve[jndex] = False
for index in range(7,limit):
    if sieve[index]:
        results.append(index)
return results

Например, когда я генерирую простые простые просты на пределе 1000, Sieve Atkin пропускается Prime 997, но включает в себя композит 965. Но если я генерирую до предела 5000, список его возврата, полностью правильно.

Answer 1

• Изменять lim к limit. Отказ Конечно, вы, должно быть, знали это.
• С sieve = [False]*limit, самый большой индекс, допустимый limit-1.

  Однако на этой линии

  if (n <= limit) and (n % 12 == 1 or n % 12 == 5):
  

  Вы проверяете, если n<=limit. Отказ Если n==limit тогда sieve[n] поднимает индексэрмер. Попробуйте свой алгоритм с небольшим значением limit (например, n = 50). Вы увидите эту ошибку. Простое исправление - использовать

  sieve = [False]*(limit+1)
  

  Легкое исправление немного расточительно, поскольку сито [0] никогда не используется. Так что вы могли бы подумать лучшее решение, чтобы сохранить sieve = [False]*limit, но исправьте все свой другой код, наступив индекс на sieve вниз за другим. (Например, изменить sieve[n] к sieve[n-1] Везде и т. Д.) Однако это заставит вас сделать ряд дополнительных вычитаний, которые не будут хорошими для скорости. Таким образом, простое / расточительное решение на самом деле, вероятно, лучший вариант.

• Согласно с http://en.wikipedia.org/wiki/sieve_of_Atkin.X должен быть целым числом в [1, SQRT (LIMIT)], включительно в конечных точках.

  В вашем коде

  factor = int(math.sqrt(limit))
  

  а также int берет пол из math.sqrt(limit). Отказ Более того,

  range(1,factor) Идет от 1 до фактора-1. Итак, вы выходите на 1.

  Так что вам нужно изменить это на

  factor = int(math.sqrt(limit))+1
  

• Видеть Самый быстрый способ перечислить все простыни ниже n Для альтернативы (и быстрее) внедрения сита Аткина из-за Стива Кренель.

def AtkinSieve (limit):
    results = [2,3,5]
    sieve = [False]*(limit+1)
    factor = int(math.sqrt(limit))+1
    for i in range(1,factor):
        for j in range(1, factor):
            n = 4*i**2+j**2
            if (n <= limit) and (n % 12 == 1 or n % 12 == 5):
                sieve[n] = not sieve[n]
            n = 3*i**2+j**2
            if (n <= limit) and (n % 12 == 7):
                sieve[n] = not sieve[n]
            if i>j:
                n = 3*i**2-j**2
                if (n <= limit) and (n % 12 == 11):
                    sieve[n] = not sieve[n]
    for index in range(5,factor):
        if sieve[index]:
            for jndex in range(index**2, limit, index**2):
                sieve[jndex] = False
    for index in range(7,limit):
        if sieve[index]:
            results.append(index)
    return results