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

Đây là chương trình C++ triển khai Sàng Eratosthenes (Sieve of Eratosthenes) để tạo các số nguyên tố trong một khoảng cho trước. Trong phương pháp này, một mảng số nguyên với tất cả các phần tử được khởi tạo bằng 0.

Nó tuân theo quy tắc: chỉ số của từng phần tử không phải số nguyên tố được đánh dấu là 1 bên trong các vòng lặp lồng nhau. Các số nguyên tố là những số có chỉ số được đánh dấu là 0.

Thuật toán

Bắt đầu
    Khai báo mảng kích thước n và khởi tạo bằng 0
    Khai báo length, i, j
    Đọc length
    For i = 2 đến n-1
        For j = i*i đến n-1
            Arr[j-1] = 1
    For i = 1 đến n
        If(arr[i-1] == 0)
            In i
Kết thúc

Mã ví dụ

#include <iostream>
const int len = 30;
int main() {
    int arr[30] = {0};
    for (int i = 2; i < 30; i++) {
        for (int j = i * i; j < 30; j += i) {
            arr[j - 1] = 1;
        }
    }
    for (int i = 1; i < 30; i++) {
        if (arr[i - 1] == 0)
            std::cout << i << "\t";
    }
}

Kết quả đầu ra

1 2 3 5 7 11 13 17 19 23 29