Pourquoi ma mise en œuvre du Crible d'Atkin donnant des numéros proches de la limite spécifiée?

Question

Ma mise en œuvre de Crible d'Atkin soit offre une vue sur les nombres premiers près de la limite ou composites près de la limite . alors que certaines limites de travail et d'autres ne le font pas. Je suis complètement confus quant à ce qui ne va pas.

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

Par exemple, quand je produis un nombres premiers à la limite de 1000, le tamis Atkin manque le premier 997, mais comprend le 965. composite Mais si je produis la limite de 5000, la liste qu'il renvoie est tout à fait correct.

Answer 1

• Modifier lim à limit. Bien sûr, vous devez avoir le savoir.
• Depuis sieve = [False]*limit, le plus grand indice autorisé est limit-1.

  Cependant, sur cette ligne

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

  vous vérifiez si n<=limit. Si n==limit puis sieve[n] soulève une IndexError. Essayez votre algorithme avec une petite valeur de limit (par exemple n = 50). Vous verrez cette erreur venir. Une solution facile est d'utiliser

  sieve = [False]*(limit+1)
  

  La solution facile est un peu inutile car tamis [0] est jamais utilisé. Donc, vous pourriez penser une meilleure solution est de garder sieve = [False]*limit, mais corriger tous vos autres codes en renforçant l'index sur sieve par un. (Par exemple, le changement sieve[n] à sieve[n-1] partout, etc.) Toutefois, cela vous obligera à faire un certain nombre de soustractions supplémentaires qui ne sera pas bon pour la vitesse. Donc, la solution facile / gaspillage est en fait probablement la meilleure option.

• Selon http: //en.wikipedia. org / wiki / Sieve_of_Atkin , x doit être un nombre entier dans [1, sqrt (limite)], y compris des points d'extrémité.

  Dans votre code

  factor = int(math.sqrt(limit))
  

  et int prend étage de math.sqrt(limit). En outre,

  range(1,factor) va de 1 à facteur 1. Donc, vous êtes hors de 1.

  Vous devez changer pour

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

• Voir moyen le plus rapide à la liste ci-dessous tous les nombres premiers N une alternative (et plus rapide) mise en œuvre du crible d'Atkin, en raison de Steve Krenzel.

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