Thuật toán tìm số nguyên tố với C++

Thuật toán sàng nguyên tố là một thuật toán được sử dụng để tìm tất cả các số nguyên tố nhỏ hơn hoặc bằng một giới hạn cho trước. Thuật toán sàng nguyên tố được gọi là “sàng” vì nó loại bỏ các ước số của các số nguyên tố để tìm các số nguyên tố.

Có nhiều cách để cài đặt thuật toán sàng nguyên tố, tuy nhiên một cách cơ bản là sử dụng một mảng để lưu trữ các số nguyên và đánh dấu các số nguyên tố. Cụ thể, thuật toán bắt đầu với một mảng ban đầu các giá trị đều là true, sau đó loại bỏ các giá trị không phải số nguyên tố bằng cách đánh dấu các ước số của các số nguyên tố là false. Sau khi hoàn thành việc đánh dấu, các phần tử còn lại có giá trị true trong mảng là các số nguyên tố.

Dưới đây là một ví dụ về thuật toán sàng nguyên tố trong C++:

#include <iostream>
#include <cmath>
using namespace std;

void SieveOfEratosthenes(int n) {
    bool isPrime[n+1];
    for (int i = 2; i <= n; i++) {
        isPrime[i] = true;
    }

    for (int i = 2; i <= sqrt(n); i++) {
        if (isPrime[i]) {
            for (int j = i*i; j <= n; j += i) {
                isPrime[j] = false;
            }
        }
    }

    for (int i = 2; i <= n; i++) {
        if (isPrime[i]) {
            cout << i << " ";
        }
    }
}

int main() {
    int n;
    cout << "Nhap gioi han n: ";
    cin >> n;
    cout << "Cac so nguyen to nho hon hoac bang " << n << " la: ";
    SieveOfEratosthenes(n);
    return 0;
}