Số học 2 - Số nguyên tố, Sàng Eratosthenes, O (1), O (n log n) và O (log n) là gì

 Nguồn: HackerEarth và 1 số bài viết trên Wikipedia

Người dịch: Bùi Việt Dũng

Table of Contents

• Số nguyên tố (Prime Numbers)
  • Thuật toán "ngây thơ"
  • Một thuật toán tốt hơn
• Sàng Eratosthenes (Sieve of Eratosthenes)
• Phân tích thừa số nguyên tố với sàng Eratosthenes
• Sàng Eratosthenes trên đoạn
• Bài tập áp dụng:

Bạn có thể đọc phần 1 về Modulo & GCD ở đây.

Số nguyên tố (Prime Numbers)

Số nguyên tố là số nguyên lớn hơn 1 và có đúng 2 ước là 1 và chính nó.

Hợp số (Composite numbers) là số nguyên lớn hơn 1 và có nhiều hơn 2 ước.

Ví dụ, 5 là số nguyên tố vì 5 chỉ chia hết cho 1 và 5. Tuy nhiên, 6 là hợp số vì 6 chia hết cho 1, 2, 3 và 6.

Có rất nhiều phương pháp để kiểm tra một số nguyên có phải là số nguyên tố hay không.

Thuật toán "ngây thơ"

Ta sẽ duyệt hết tất cả các số từ 1 đến 𝑁$N$ và đếm số ước của 𝑁$N$. Nếu số ước của 𝑁$N$ là 2 thì 𝑁$N$ là số nguyên tố, nếu không thì 𝑁$N$ không là số nguyên tố.

bool isPrime(int n) {
    for (int i = 2; i < n; i++)
        if (n % i == 0) {
            // n chia hết cho số khác 1 và chính nó.
            return false;
        }
    return n > 1;
}

Độ phức tạp của thuật toán: Độ phức tạp của thuật toán là 𝑂(𝑁)$O(N)$ do ta phải duyệt hết các số từ 1 đến 𝑁$N$.

Một thuật toán tốt hơn

Xét hai số nguyên dương 𝑁$N$ và 𝐷$D$ thỏa mãn 𝑁$N$ chia hết cho 𝐷$D$ và 𝐷$D$ nhỏ hơn 𝑁‾‾√$\sqrt{N}$. Khi đó 𝑁𝐷$\frac{N}{D}$ phải lớn hơn 𝑁‾‾√$\sqrt{N}$. 𝑁$N$ cũng chia hết cho 𝑁𝐷$\frac{N}{D}$. Vì thế, nếu 𝑁$N$ có ước nhỏ hơn 𝑁‾‾√$\sqrt{N}$ thì 𝑁$N$ cũng có ước lớn hơn 𝑁‾‾√$\sqrt{N}$. Do đó, ta chỉ cần duyệt đến 𝑁‾‾√$\sqrt{N}$.

bool isPrime(int n) {
    for (int i = 2; i*i <= n; i++)
        if (n % i == 0) return false;
    return n > 1;
}

Độ phức tạp của thuật toán: Độ phức tạp của thuật toán là 𝑂(𝑁‾‾√)$O(\sqrt{N})$ do ta phải duyệt từ 1 đến 𝑁‾‾√$\sqrt{N}$.

Sàng Eratosthenes (Sieve of Eratosthenes)

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 đó. Nó còn có thể được sử dụng để kiểm tra một số nguyên nhỏ hơn hoặc bằng 𝑁$N$ hay không.

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ố.

Mã giả (Pseudo Code):

• Đánh dấu tất cả các số đều là số nguyên tố.

• Với mỗi số nguyên tố nhỏ hơn 𝑁‾‾√$\sqrt{N}$

  • Đánh dấu các bội lớn hơn nó là số nguyên tố.

void sieve(int N) {
    bool isPrime[N+1];
    for(int i = 0; i <= N;++i) {
        isPrime[i] = true;
    }
    isPrime[0] = false;
    isPrime[1] = false;
    for(int i = 2; i * i <= N; ++i) {
         if(isPrime[i] == true) {
             // Mark all the multiples of i as composite numbers
             for(int j = i * i; j <= N; j += i)
                 isPrime[j] = false;
        }
    }
}

Code trên được dùng để tìm các số nguyên tố nhỏ hơn hoặc bằng 𝑁$N$.

Độ phức tạp của thuật toán:

Số lần lặp của vòng lặp trong là:

• Khi 𝑖=2$i=2$, vòng lặp trong lặp 𝑁2$\frac{N}{2}$ lần.
• Khi 𝑖=3$i=3$, vòng lặp trong lặp 𝑁3$\frac{N}{3}$ lần.
• Khi 𝑖=5$i=5$, vòng lặp trong lặp 𝑁5$\frac{N}{5}$ lần.
• …

Độ phức tạp tổng: 𝑁.(12+13+15+…)=𝑂(𝑁log𝑁)$N.(\frac{1}{2}+\frac{1}{3}+\frac{1}{5}+\dots )=O(N\log N)$.

Phân tích thừa số nguyên tố với sàng Eratosthenes

Cách cài đặt:

Đầu tiên hãy xem xét thuật toán phân tích ra thừa số nguyên tố trong 𝑂(𝑁‾‾√)$O(\sqrt{N})$.

vector<int> factorize(int n) {
    vector<int> res;
    for (int i = 2; i * i <= n; ++i) {
        while (n % i == 0) {
            res.push_back(i);
            n /= i;
        }
    }
    if (n != 1) {
        res.push_back(n);
    }
    return res;
}

Tại mỗi bước ta phải tìm số nguyên tố nhỏ nhất mà 𝑁$N$ chia hết cho số đó. Do đó, ta phải biến đổi sàng Eratosthenes để tìm được số mình mong muốn trong 𝑂(1)$O(1)$.

int minPrime[n + 1];
for (int i = 2; i * i <= n; ++i) {
    if (minPrime[i] == 0) { //if i is prime
        for (int j = i * i; j <= n; j += i) {
            if (minPrime[j] == 0) {
                minPrime[j] = i;
            }
        }
    }
}
for (int i = 2; i <= n; ++i) {
    if (minPrime[i] == 0) {
        minPrime[i] = i;
    }
}

Bây giờ ta có thể phân tích một số ra thừa số nguyên tố trong 𝑂(log𝑁)$O(\log N)$.

vector<int> factorize(int n) {
    vector<int> res;
    while (n != 1) {
        res.push_back(minPrime[n]);
        n /= minPrime[n];
    }
    return res;
}

Điều kiện sử dụng phương pháp này là ta phải tạo được mảng có độ dài 𝑁$N$ phần tử.

Phương pháp này rất hữu ích khi ta phải phân tich nhiều số nhỏ ra thừa số nguyên tố. Ta không cần thiết phải sử dụng phương pháp này trong mọi bài toán liên quan đến phân tích một số ra thừa số nguyên tố. Ngoài ra, ta không thể sử dụng phương pháp này nếu 𝑁$N$ bằng 109${10}^9$ hay 1012${10}^{1}2$. Khi đó, ta chỉ có thể sử dụng thuật toán 𝑂(𝑁‾‾√)$O(\sqrt{N})$.

Tính chất thú vị: Nếu 𝑁=𝑝𝑞11.𝑝𝑞22…𝑝𝑞𝑘𝑘$N=p_1^{q_1}.p_2^{q_2}\dots p_k^{q_k}$ với 𝑝1,𝑝2,…,𝑝𝑘$p_1,p_2,\dots ,p_k$ là các số nguyên tố thì 𝑁$N$ có (𝑞1+1).(𝑞2+1)…(𝑞𝑘+1)$(q_1+1).(q_2+1)\dots (q_k+1)$ ước phân biệt.

Sàng Eratosthenes trên đoạn

Đôi khi bạn phải tìm tất cả các số không phải trên đoạn [1;𝑁]$[1;N]$ mà là trên đoạn [𝐿;𝑅]$[L;R]$ với 𝑅$R$ lớn.

Điều kiện sử dụng phương pháp này là bạn có thể tạo mảng độ dài 𝑅−𝐿+1$R-L+1$ phần tử.

Cài đặt:

vector<bool> isPrime(R - L + 1, true);  // x là số nguyên tố khi và chỉ khi isPrime[x - l] == true

for (long long i = 2; i * i <= R; ++i) {
    for (long long j = max(i * i, (L + i - 1) / i * i); j <= R; j += i) {
        isPrime[j - L] = false;
    }
}

if (1 >= L) {  // Xét riêng trường hợp số 1
    isPrime[1 - L] = false;
}

for (long long x = L; x <= R; ++x) {
    if (isPrime[x - L]) {
        // i là số nguyên tố
    }
}

Độ phức tạp của thuật toán là 𝑂(𝑅‾‾√∗𝑘)$O(\sqrt{R}\ast k)$ với 𝑘$k$ là hằng số.

Lưu ý: Nếu bạn chỉ cần kiểm tra tính nguyên tố của một hay một vài số thì ta không nhất thiết phải xây dựng sàng. Ta có thể sử dụng hàm sau để kiểm tra tính nguyên tố của một số.

bool isPrime(int n) {
    for (int i = 2; i * i <= n; ++i) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

Bài tập áp dụng:

• SPOJ - PRIME1
• VOJ - NKABD