غربال أتكين

n -= 2 * y2; // Оптимизация

• if ((i> j) && (n <= limit) && (n % 12 == 11))
• is_prime[n] = !is_prime[n];
• }

y2 = 0;

• for (j = 1; j <= sqr_lim; j++) {
• y2 += 2 * j - 1;
• n = 4 * x2 + y2;

is_prime[n] = !is_prime[n];

// n = 3 * x2 + y2;

n = i * i;

• for (j = n; j <= limit; j += n) {
• is_prime[j] = false;
• }
• }

is_prime[3] = true;

• // Предположительно простые - это целые с нечетным числом
• // представлений в данных квадратных формах.
• // x2 и y2 - это квадраты i и j (оптимизация).

n:=n-2*sqr(y);

• if (x>y) and (n<=limit) and (n mod 12 = 11) then
• is_prime[n]:=not is_prime[n];
• end;
• for i:=5 to trunc(sqrt(limit)) do
• begin
• if is_prime[i] then
• begin
• k:=sqr(i);
• n:=k;
• while n<=limit do
• begin
• is_prime[n]:=false;
• n:=n+k;
• end;
• end;
• end;
• is_prime[2]:=true;
• is_prime[3]:=true;
• end;
• begin
• dosieve(10000);
• for jj:=1 to 10000 do
• if is_prime[jj] then

printf("2, 3, 5");

• if ((is_prime[i]) && (i % 3 != 0) && (i % 5 != 0)){
• printf(", %d", i);
• }
• }

إضافةً إلى ذلك، for (i = 6; i <= limit; i++) { // добавлена проверка делимости на 3 и 5. В оригинальной версии алгоритма потребности в ней нет.

sqr_lim = (int)sqrt((long double)limit);

is_prime[2] = true;

for (i = 0; i <= limit; i++) is_prime[i] = false;

n:=4*sqr(x)+sqr(y);

if (n<=limit) and ((n mod 12 = 1) or (n mod 12 = 5)) then

is_prime[n]:=not is_prime[n];

}

• // Отсеиваем кратные квадратам простых чисел в интервале [5, sqrt(limit)].
• // (основной этап не может их отсеять)
• for (i = 5; i <= sqr_lim; i++) {
• if (is_prime[i]) {

}

// Вывод списка простых чисел в консоль.

n -= x2; // Оптимизация

if ((n <= limit) && (n % 12 == 7))

n:=n-sqr(x);

is_prime[n]:=not is_prime[n];

if (n<=limit) and (n mod 12 = 7) then

writeln(jj);

• end.
• النسخة المبسطة للخوارزمية
• int limit = 1000;
• int sqr_lim;
• bool is_prime[1001];
• int x2, y2;
• int i, j;
• int n;
• // Инициализация решета

is_prime[n] = !is_prime[n];

// n = 3 * x2 - y2;

x2 = 0;

for (i = 1; i <= sqr_lim; i++) {

x2 += 2 * i - 1;