لماذا يعتبر تنفيذ غربال Atkin يطل على الأرقام القريبة من الحد المحدد؟

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 ، يفتقد غربال 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 (على سبيل المثال ن = 50). سترى هذا الخطأ يأتي. حل سهل هو الاستخدام

  sieve = [False]*(limit+1)
  

  يعد الإصلاح السهل مضيئًا بعض الشيء نظرًا لأن Sieve [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 لتنفيذ بديل (وأسرع) لخلال Atkin ، بسبب 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