غربال اتکین

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

غربال آتکین (به انگلیسی: Sieve of Atkin) الگوریتمی برای پیدا کردن اعداد اول است. این روش از غربال اراتوستن سریع‌تر و پیچیده‌تر است.

پیچیدگی محاسباتی[ویرایش]

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

شبه‌کد[ویرایش]

// arbitrary search limit
limit ← 1000000         

// 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] × [1, √limit]:
    n ← 4x²+y²
    if (n ≤ limit) ∧ (n mod 12 = 1 ∨ n mod 12 = 5):
        is_prime(n) ← ‌is_prime(n)
    n ← 3x²+y²
    if (n ≤ limit) ∧ (n mod 12 = 7):
        is_prime(n) ← ‌is_prime(n)
    n ← 3x²-y²
    if (x > y) ∧ (n ≤ limit) ∧ (n mod 12 = 11):
        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

منبع[ویرایش]

  1. A.O.L. Atkin, D.J. Bernstein, Prime sieves using binary quadratic forms, Math. Comp., Vol. 73 (2004), 1023-1030.