
_START_ARTICLE_
غربال أتكين
_START_PARAGRAPH_
في الرياضيات، غربال أتكين هو خوارزمية سريعة وعصرية لإيجاد جميع الأعداد الأولية الأصغر من عدد ما. هو صيغة متطورة للغربال القديم والمعروف بغربال إراتوستينس._NEWLINE_نظرت هاته الخوارزمية من طرف العالمين أرثور أوليفر لوندال أتكين ودانييل يوليوس بيرنشتاين.
_START_SECTION_
نسخة الخوارزمية على لغة الباسكال
_START_PARAGRAPH_
program atkin;var is_prime:array[1..10001] of boolean; jj:int64;procedure dosieve(limit:int64);var i,k,x,y:int64; n:int64;begin_NEWLINE_  for i:=5 to limit do_NEWLINE_    is_prime[i]:=false;_NEWLINE_  for x:=1 to trunc(sqrt(limit)) do_NEWLINE_    for y:=1 to trunc(sqrt(limit)) do_NEWLINE_    begin_NEWLINE_      n:=4*sqr(x)+sqr(y);_NEWLINE_      if (n<=limit) and ((n mod 12 = 1) or (n mod 12 = 5)) then_NEWLINE_        is_prime[n]:=not is_prime[n];_NEWLINE_      n:=n-sqr(x);_NEWLINE_      if (n<=limit) and (n mod 12 = 7) then_NEWLINE_        is_prime[n]:=not is_prime[n];_NEWLINE_      n:=n-2*sqr(y);_NEWLINE_      if (x>y) and (n<=limit) and (n mod 12 = 11) then_NEWLINE_        is_prime[n]:=not is_prime[n];_NEWLINE_    end;_NEWLINE_  for i:=5 to trunc(sqrt(limit)) do_NEWLINE_  begin_NEWLINE_    if is_prime[i] then_NEWLINE_    begin_NEWLINE_      k:=sqr(i);_NEWLINE_      n:=k;_NEWLINE_      while n<=limit do_NEWLINE_      begin_NEWLINE_        is_prime[n]:=false;_NEWLINE_        n:=n+k;_NEWLINE_      end;_NEWLINE_    end;_NEWLINE_  end;_NEWLINE_  is_prime[2]:=true;_NEWLINE_  is_prime[3]:=true;end;begin_NEWLINE_  dosieve(10000);_NEWLINE_  for jj:=1 to 10000 do_NEWLINE_    if is_prime[jj] then_NEWLINE_      writeln(jj);end.
_START_SECTION_
النسخة المبسطة للخوارزمية
_START_PARAGRAPH_
int limit = 1000;int sqr_lim;bool is_prime[1001];int x2, y2;int i, j;int n;// Инициализация решетаsqr_lim = (int)sqrt((long double)limit);for (i = 0; i <= limit; i++) is_prime[i] = false;is_prime[2] = true;is_prime[3] = true;// Предположительно простые - это целые с нечетным числом// представлений в данных квадратных формах.// x2 и y2 - это квадраты i и j (оптимизация).x2 = 0;for (i = 1; i <= sqr_lim; i++) {_NEWLINE_    x2 += 2 * i - 1;_NEWLINE_    y2 = 0;_NEWLINE_    for (j = 1; j <= sqr_lim; j++) {_NEWLINE_        y2 += 2 * j - 1;_NEWLINE_        _NEWLINE_        n = 4 * x2 + y2;_NEWLINE_        if ((n <= limit) && (n % 12 == 1 || n % 12 == 5))_NEWLINE_            is_prime[n] = !is_prime[n];_NEWLINE_        _NEWLINE_        // n = 3 * x2 + y2; _NEWLINE_        n -= x2; // Оптимизация_NEWLINE_        if ((n <= limit) && (n % 12 == 7))_NEWLINE_            is_prime[n] = !is_prime[n];_NEWLINE_        _NEWLINE_        // n = 3 * x2 - y2;_NEWLINE_        n -= 2 * y2; // Оптимизация_NEWLINE_        if ((i> j) && (n <= limit) && (n % 12 == 11))_NEWLINE_            is_prime[n] = !is_prime[n];_NEWLINE_    }}// Отсеиваем кратные квадратам простых чисел в интервале [5, sqrt(limit)].// (основной этап не может их отсеять)for (i = 5; i <= sqr_lim; i++) {_NEWLINE_    if (is_prime[i]) {_NEWLINE_        n = i * i;_NEWLINE_        for (j = n; j <= limit; j += n) {_NEWLINE_            is_prime[j] = false;_NEWLINE_        }_NEWLINE_    }}// Вывод списка простых чисел в консоль.printf("2, 3, 5"); _NEWLINE_for (i = 6; i <= limit; i++) {  // добавлена проверка делимости на 3 и 5. В оригинальной версии алгоритма потребности в ней нет._NEWLINE_    if ((is_prime[i]) && (i % 3 != 0) && (i % 5 !=  0)){_NEWLINE_       printf(", %d", i);_NEWLINE_    }}