Chương trình C++ triển khai sàng phân đoạn (Segmented Sieve) tạo số nguyên tố

Đây là chương trình C++ triển khai Sàng phân đoạn (Segmented Sieve) để tạo các số nguyên tố trong một khoảng cho trước. Sàng phân đoạn đầu tiên sử dụng Sàng đơn giản (Simple Sieve) để tìm các số nguyên tố nhỏ hơn hoặc bằng √n. Ý tưởng của thuật toán này là chia khoảng [0 ... n-1] thành các đoạn khác nhau và tính toán số nguyên tố trong tất cả các đoạn một cách lần lượt.

Thuật toán

Bắt đầu
    Tạo hàm tìm tất cả số nguyên tố nhỏ hơn limit
    sử dụng sàng Eratosthenes đơn giản.
    Tìm tất cả số nguyên tố trong khoảng cho trước dùng
    sàng phân đoạn
    A) Tính tất cả số nguyên tố nhỏ hơn hoặc bằng căn bậc hai của high dùng sàng đơn giản
    B) Đếm số phần tử trong khoảng cho trước
    C) Khai báo mảng boolean chỉ cho [low, high]
    D) Tìm số nhỏ nhất trong [low ... high] là bội của prime[i] (chia hết cho prime[i])
    E) Đánh dấu các bội của prime[i] trong [low … high]
    F) Các số không bị đánh dấu trong khoảng là số nguyên tố
Kết thúc

Mã ví dụ

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

void simpleSieve(int lmt, vector<int>& prime) {
    bool mark[lmt + 1];
    memset(mark, false, sizeof(mark));
    for (int i = 2; i <= lmt; ++i) {
        if (mark[i] == false) {
            prime.push_back(i);
            for (int j = i; j <= lmt; j += i)
                mark[j] = true;
        }
    }
}

void PrimeInRange(int low, int high) {
    int lmt = floor(sqrt(high)) + 1;
    vector<int> prime;
    simpleSieve(lmt, prime);
    int n = high - low + 1;
    bool mark[n + 1];
    memset(mark, false, sizeof(mark));
    for (int i = 0; i < prime.size(); i++) {
        int lowLim = floor(low / prime[i]) * prime[i];
        if (lowLim < low)
            lowLim += prime[i];
        for (int j = lowLim; j <= high; j += prime[i])
            mark[j - low] = true;
    }
    for (int i = low; i <= high; i++)
        if (!mark[i - low])
            cout << i << " ";
}

int main() {
    int low = 10, high = 50;
    PrimeInRange(low, high);
    return 0;
}

Kết quả đầu ra

11 13 17 19 23 29 31 37 41 43 47