Chương trình C++ triển khai sàng Atkin tạo số nguyên tố

Đây là chương trình C++ triển khai Sàng Atkin (Sieve of Atkin) để tạo các số nguyên tố trong một khoảng cho trước. Sàng Atkin là một thuật toán hiện đại để tìm tất cả các số nguyên tố lên đến một số nguyên xác định.

Thuật toán

Bắt đầu
    Tạo danh sách kết quả, điền sẵn 2, 3, và 5.
    Khởi tạo mảng sàng với giá trị false
    Đánh dấu siev[n] là true nếu một trong các điều kiện sau đúng:
    a) n = (4*x*x) + (y*y) có số nghiệm lẻ
       n % 12 = 1 hoặc n % 12 = 5.
    b) n = (3*x*x) + (y*y) có số nghiệm lẻ và n % 12 = 7
    c) n = (3*x*x) - (y*y) có số nghiệm lẻ, x > y và n % 12 = 11
    Đánh dấu tất cả bội của bình phương là không phải số nguyên tố
    In các số nguyên tố dùng mảng sieve[]
Kết thúc

Mã ví dụ

#include <bits/stdc++.h>
using namespace std;

int SieveOfAtkin(int lmt) {
    if (lmt > 2)
        cout << 2 << " ";
    if (lmt > 3)
        cout << 3 << " ";
    bool sieve[lmt];
    for (int i = 0; i < lmt; i++)
        sieve[i] = false;
    for (int a = 1; a * a < lmt; a++) {
        for (int b = 1; b * b < lmt; b++) {
            // Phần chính của Sàng Atkin
            int n = (4 * a * a) + (b * b);
            if (n <= lmt && (n % 12 == 1 || n % 12 == 5))
                sieve[n] ^= true;
            n = (3 * a * a) + (b * b);
            if (n <= lmt && n % 12 == 7)
                sieve[n] ^= true;
            n = (3 * a * a) - (b * b);
            if (a > b && n <= lmt && n % 12 == 11)
                sieve[n] ^= true;
        }
    }
    for (int r = 5; r * r < lmt; r++) {
        if (sieve[r]) {
            for (int i = r * r; i < lmt; i += r * r)
                sieve[i] = false;
        }
    }
    for (int x = 5; x < lmt; x++)
        if (sieve[x])
            cout << x << " ";
}

int main(void) {
    int lmt = 30;
    SieveOfAtkin(lmt);
    return 0;
}

Kết quả đầu ra

2 3 5 7 11 13 17 19 23 29