Sàng nguyên tố
đã đăng vào 11, Tháng 2, 2026, 2:18* Sàng nguyên tố Eratosthenes (Sieve of Eratosthenes)
Hướng tiếp cận Ban đầu, ta cho tất cả các số từ 2 đến n vào sàng và đánh dấu tất cả các số. (Các số không được đánh dấu sau cùng sẽ bị loại khỏi sàng). Duyệt lần lượt các số từ 2 đến n. Nếu số đang xét:
Đã được đánh dấu
⇒ số nguyên tố: ta bỏ đánh dấu tất cả các bội (khác chính nó) của số nguyên tố này để loại các bội ấy ra khỏi sàng.
Không được đánh dấu
⇒ hợp số: ta bỏ qua số này. Sau khi duyệt xong, các số còn lại trong sàng, hay nói cách khác các số được đánh dấu là số nguyên tố.
Ta có thể hiểu như hình dưới đây:
Code C++ minh họa
const int maxn = 1000000 + 5; //10^6 + 5
bool is_prime[maxn]; // mảng bool khởi tạo với các giá trị false
void sieve(int n){
// Đánh dấu các số từ 2 đến n đều là số nguyên tố
for (int i = 2; i <= n; i++)
is_prime[i] = true;
for (int i = 2; i <= n; i++) {
if (is_prime[i]) {
for (int j = i * 2; j <= n; j += i)
// Bỏ đánh dấu tất cả các số không phải số nguyên tố
is_prime[j] = false;
}
}
}
Độ phức tạp thời gian là O(n*(1/2+1/3+...+1/p) với p là số nguyên tố <= n.
Độ phức tạp thời gian là O(n log log n)
Đô phức tạp không gian là O(n)
Dựa vào Nhận xét trên, ta có cải tiến như sau:
CODE MẪU :
const int maxn = 1000000 + 5; //10^6 + 5
bool is_prime[maxn];
void Eratosthenes(int n){
for (int i = 2; i <= n; i++)
is_prime[i] = true;
for (int i = 2; i * i <= n; i++) {
if (is_prime[i]) {
// j sẽ bắt đầu chạy từ i * i
for (int j = i * i; j <= n; j += i)
is_prime[j] = false;
}
}
}
Độ phức tạp thời gian vẫn vậy.Tuy nhiên, số phép tính đã giảm đi đáng kể.
