Chương trình C++ tạo số nguyên tố trong khoảng cho trước bằng sàng Sundaram

Đây là chương trình C++ triển khai sàng Sundaram để tạo các số nguyên tố trong một khoảng cho trước. Thuật toán này được phát hiện năm 1934 bởi Sundaram.

Thuật toán

Bắt đầu printPrimes(n)
    Ở đây chúng ta tìm các số nguyên tố nhỏ hơn n, giảm n-2 xuống một nửa. Gọi là New.
    New = (n-2)/2;
    Tạo mảng marked[n] để phân tách các số dạng i+j+2ij với những số khác, trong đó 1 <= i <= j
    Khởi tạo tất cả các phần tử của marked[] là false.
    Đánh dấu tất cả các số dạng i + j + 2ij là true với 1 <= i <= j
    for i = 1 đến New
        a) j = i;
        b) Vòng lặp While (i + j + 2*i*j) <= New
            marked[i + j + 2*i*j] = true
            j++
    if n > 2, in 2 là số nguyên tố đầu tiên.
    Các số nguyên tố còn lại có dạng 2i + 1 với i là chỉ số của các số KHÔNG bị đánh dấu.
    In 2i + 1 cho tất cả i sao cho marked[i] là false.
Kết thúc

Mã ví dụ

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

int SieveOfSundaram(int m) {
    int N = (m - 2) / 2;
    bool marked[N + 1];
    memset(marked, false, sizeof(marked));
    for (int i = 1; i <= N; i++)
        for (int j = i; (i + j + 2 * i * j) <= N; j++)
            marked[i + j + 2 * i * j] = true;

    if (m > 2)
        cout << 2 << " ";
    for (int i = 1; i <= N; i++)
        if (marked[i] == false)
            cout << 2 * i + 1 << " ";
}

int main(void) {
    int m = 10;
    SieveOfSundaram(m);
    return 0;
}

Kết quả đầu ra

2 3 5 7