غربال اتکین

غربال آتکین (به انگلیسی: Sieve of Atkin) الگوریتمی برای پیدا کردن اعداد اول است. این روش از غربال اراتوستن سریع‌تر و پیچیده‌تر است. در مقایسه با غربال باستانی اراتوستن، که مضرب‌های اعداد اول را مشخص می‌کند، غربال اتکین کارهای مقدماتی را انجام می‌دهد و سپس مضرب مربع‌های اول را مشخص می‌کند، بنابراین به پیچیدگی مجانبی نظری بهتری دست می‌یابد. در سال ۲۰۰۳ توسط A. O. L. Atkin و Daniel J. Bernstein ایجاد شد.

پیچیدگی محاسباتی

پیچیدگی محاسباتی این الگوریتم برای محاسبه تعداد اعداد اول کوچکتر از N برابر است با ‎$O(N/loglogN)$‎ عمل جمع و حافظه مورد نیاز برابر با ‎$N^{1/2+o(1)}$‎ می‌باشد.

شبه‌کد

کد زیر شبه کدی است که الگوریتم‌های اتکین ۳٫۱، ۳٫۲ و ۳٫۳ را با استفاده از مجموعه ترکیبی "s" از همه اعداد مدول ۶۰ به استثنای مواردی که مضربی از اعداد اول ۲، ۳ و ۵ هستند، ترکیب می‌کند. الگوریتم‌ها، برای یک نسخه ساده از الگوریتم که از بسته‌بندی بیت اختیاری چرخ پشتیبانی می‌کند. اگرچه به‌طور خاص در مقاله ارجاع شده ذکر نشده‌است، این شبه کد برخی از ترکیبات آشکار x/yهای فرد/ زوج را حذف می‌کند تا محاسبات را در جایی که آن محاسبات هرگز آزمون‌های مدول را پشت سر نمی‌گذارند (یعنی اعداد زوج یا مضرب‌های ۳ یا ۵ تولید کنند) کاهش می‌دهد):

// arbitrary search limit
limit ← ۱۰۰۰۰۰۰

// initialize the sieve
is_prime(i) ← false, i ∈ [5, limit]

// put in candidate primes:
// integers which have an odd number of
// representations by certain quadratic forms
for (x, y) in [1, √limit] × [۱, √limit]:
  n ← 4x²+y²
  if (n ≤ limit) ∧ (n mod 12 = ۱ ∨ n mod 12 = ۵):
  is_prime(n) ← is_prime(n)
  n ← 3x²+y²
  if (n ≤ limit) ∧ (n mod 12 = ۷):
  is_prime(n) ← is_prime(n)
  n ← 3x²-y²
  if (x > y) ∧ (n ≤ limit) ∧ (n mod 12 = ۱۱):
  is_prime(n) ← is_prime(n)

// eliminate composites by sieving
for n in [5, √limit]:
  if is_prime(n):
        // n is prime, omit multiples of its square; this is
        // sufficient because composites which managed to get
        // on the list cannot be square-free
  is_prime(k) ← false, k ∈ {n², 2n², 3n², … , limit}

print 2, 3
for n in [5, limit]:
  if is_prime(n): print n

پیچیدگی محاسباتی

می‌توان محاسبه کرد که سری‌های سه عملیات معادله درجه دوم هر کدام تعدادی عملیات دارند که نسبت ثابتی از محدوده زمانی است که دامنه به بی‌نهایت می‌رود. همچنین عملیات حذف بدون مربع اصلی را می‌توان با تابع زتای اول (۲) با افست‌ها و فاکتورهای ثابت توصیف کرد، بنابراین با رفتن محدوده به بی‌نهایت، یک فاکتور ثابت در محدوده است؛ بنابراین، الگوریتم شرح داده شده در بالا می‌تواند اعداد اول را تا N با استفاده از عملیات O(N) تنها با بیت‌های O(N) محاسبه کند.