let menu = ["Home", "Algorithms", "CodeHub", "VNOI Statistics"];

Sàng nguyên tố Eratosthenes

Sàng nguyên tố Eratosthenes

Contents

Mục đích của sàng nguyên tố Eratosthenes là tìm tất cả các số nguyên tố nhỏ hơn \(N\) cho trước.

Thuật toán

  • B1: Tạo danh sách các số nguyên từ 2 đến N: \((2, 3,..., N)\).
  • B2: Giả sử tất cả các số trong danh sách đều là số nguyên tố. Trong đó, \(p = 2\) là số nguyên tố đầu tiên.
  • B3: Tất cả các bội số của \(p\): \(2p, 3p, 4p,...\) sẽ bị đánh dấu vì không phải là số nguyên tố.
  • B4: Tìm các số còn lại trong danh sách mà chưa bị đánh dấu và phải lớn hơn \(p\). Nếu không còn số nào, dừng tìm kiếm. Ngược lại, gán cho \(p\) giá trị bằng số nguyên tố tiếp theo và quay lại bước 3.

Khi giải thuật kết thúc, tất các số chưa bị đánh dấu trong danh sách là các số nguyên tố cần tìm.

Ví dụ

Trong ví dụ sau chúng ta sẽ tìm tất cả các số nguyên tố nhỏ hơn 30. Dãy ban đầu:

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

Số đầu tiên trong dãy là 2, ta xoá tất cả các bội số (khác 2) của 2:

2 3   5   7   9    11    13    15    17    19    21    23    25    27    29

Số tiếp theo trong dãy là 3, ta tiếp tục xoá các bộ số của 3:

2 3   5   7        11    13          17    19          23    25          29

Lặp lại quá trình trên, ta được dãy các số nguyên tố nhỏ hơn 30:

2 3   5   7        11    13          17    19          23                29

Một ví dụ khác (nguồn Wikipedia):

text

Cài đặt

Khi cài đặt thuật toán, chúng ta dùng một mảng để kiểm tra xem số đã bị xoá chưa.

Cài đặt (C++)

#include <stdio.h>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n = 0;
    // Nhập n
    cin >> n;

    // Mảng đánh dấu, mark[i] == true thì i là số nguyên tố
    vector<bool> mark(n+1, true);
    mark[0] = mark[1] = false;

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

    // Xuất các số nguyên tố trong đoạn từ 1 đến n
    for(int i = 2; i <= n; i++) {
        if (mark[i]) printf("%d ", i);
    }
    printf("\n");
}

Cải tiến thuật toán

    for(int i = 2; i*i <= n; i++) {
        if (mark[i]) {
            // Xuất phát từ `i*i` vì các hợp số trước đó đều đã bị đánh dấu
            for(int j = i*i; j <= n; j+=i) {
                mark[j] = false;
            }
        }
    }

Độ phức tạp: \(O(n \log \log n)\)

Trong giới hạn thời gian 1 giây, thuật toán có thể chạy được đến khoảng \(n = 10^7\).

Xem thêm

Comments