CLAOJ Wiki - Số nguyên tố - CLAOJ: Long An HSGS Online Judge

CLAOJ Wiki - Số nguyên tố

lds posted on Sept. 24, 2023, 8:58 p.m.

Số nguyên tố là số rất thường xuất hiện trong các bài toán học và tin học. Trong bài viết này, chúng mình sẽ giúp các bạn hiểu được bản chất của số nguyên tố và kiểm tra xem một số bất kì có phải là số nguyên tố hay không bằng các phương pháp cơ bản và phổ biến nhất. Qua đó các bạn có thể giải quyết hiệu quả các bài tập liên quan đến số nguyên tố.

1. Khái niệm

Số nguyên tố (Prime number) là số tự nhiên lớn hơn $1$ chỉ có đúng hai ước số là $1$ và chính nó. Ví dụ: $2, 3, 5, 7, 11, 13, 17,$ ... là những số nguyên tố.

Hợp số (Composite number) là số tự nhiên lớn hơn $1$ và có nhiều hơn $2$ ước. Ví dụ: $4, 9, 15, 27, 111,$ ... là những hợp số.

2. Cài đặt

Đề bài: Xét một số nguyên dương $N$ xem số đó có phải là số nguyên tố hay không.

2.1 Cài đặt ngây thơ

Nhận xét

Ta dựa vào tính chất đã nêu trên để xét. Cụ thể, ta thử chia hết $N$ cho các số từ $2$ đến $N- 1$ để tìm các ước, nếu có $1$ ước trở lên thì $N$ không phải là số nguyên tố.

Code mẫu

    bool isPrime(int n) {
        for(int i = 2; i < n; i++) { 
            if(n % i == 0) {        // nếu tìm được một ước thì nó không là số nguyên tố
                return 0;
            }
        }
        return n > 1;
    }

Độ phức tạp

Độ phức tạp thời gian: $\mathcal{O}(n)$

Độ phức tạp không gian: $\mathcal{O}(1)$

2.2 Cải tiến

Nhận xét

Ta nhận thấy rằng nếu $N$ không phải là số nguyên tố, $N$ có dạng $N=A \cdot B$ và hiển nhiên $A,B$ không thể cùng lớn hơn $\sqrt{N}$ vì nếu như vậy thì $A \cdot B > \sqrt{N} \cdot \sqrt{N}=N$. Vậy nên trong các ước số của $N$ thì ít nhất một trong các ước sẽ nhỏ hơn $\sqrt{N}$. Tóm lại, ta chỉ cần xét từ $2$ đến $\sqrt{N}$, nếu có ước trong đoạn này thì $N$ không phải là số nguyên tố .

Code mẫu

    bool isPrime(long long n) {
        for(int i = 2; i * i <= n; i++) { // chạy đến căn của n
            if(n % i == 0) {              // nếu tìm được một ước thì nó không là số nguyên tố        
                return 0;                   
            }
        }
        return n > 1;
    }

Độ phức tạp

Độ phức tạp thời gian: $\mathcal{O}(\sqrt{n})$

Độ phức tạp không gian: $\mathcal{O}(1)$

3. Sàng Eratosthenes (Sieve of Eratosthenes)

3.1 Khái niệm

Sàng Eratosthenes dùng để tìm các số nguyên tố nhỏ hơn hoặc bằng số nguyên $N$ nào đó.

Nguyên lí hoạt động của sàng là vào mỗi lần duyệt, ta chọn một số nguyên tố và loại ra khỏi sàng tất cả các bội của số nguyên tố đó mà lớn hơn số đó. Sau khi duyệt xong, các số còn lại trong sàng đều là số nguyên tố.

3.2 Code mẫu

vector <bool> prime(n + 1, true);             // khởi tạo mảng prime với giá trị true

for (int i = 2; i * i <= n; i++) {
    if (prime[i] == true) {                   // nếu i là số nguyên tố
        for (int j = i * i; j <= n; j += i) {   // thì loại bỏ các số là bội của i
            prime[j] = false;
        }
    } 
}