Thuật toán nhanh nhất tìm số nguyên tố trong C++

Sàng Eratosthenes (Sieve of Eratosthenes) là một trong những cách hiệu quả nhất để tìm các số nguyên tố nhỏ hơn n khi n nhỏ hơn khoảng 10 triệu.

Chương trình dưới đây minh họa Sàng Eratosthenes.

Ví dụ

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

void SieveOfEratosthenes(int num) {
    bool pno[num+1];
    memset(pno, true, sizeof(pno));
    for (int i = 2; i*i <= num; i++) {
        if (pno[i] == true) {
            for (int j = i*2; j <= num; j += i)
                pno[j] = false;
        }
    }
    for (int i = 2; i <= num; i++)
        if (pno[i])
            cout << i << " ";
}

int main() {
    int num = 15;
    cout << "Các số nguyên tố nhỏ hơn hoặc bằng " << num << " là: ";
    SieveOfEratosthenes(num);
    return 0;
}

Kết quả

Các số nguyên tố nhỏ hơn hoặc bằng 15 là: 2 3 5 7 11 13

Hãy hiểu chương trình trên.

Hàm SieveOfEratosthenes() tìm tất cả số nguyên tố xuất hiện trước num được cung cấp làm đối số.

void SieveOfEratosthenes(int num) {
    bool pno[num+1];
    memset(pno, true, sizeof(pno));
    for (int i = 2; i*i <= num; i++) {
        if (pno[i] == true) {
            for (int j = i*2; j <= num; j += i)
                pno[j] = false;
        }
    }
    for (int i = 2; i <= num; i++)
        if (pno[i])
            cout << i << " ";
}

Hàm main() đặt giá trị num và in tất cả số nguyên tố nhỏ hơn hoặc bằng num bằng cách gọi hàm SieveOfEratosthenes().

int main() {
    int num = 15;
    cout << "Các số nguyên tố nhỏ hơn hoặc bằng " << num << " là: ";
    SieveOfEratosthenes(num);
    return 0;
}