Tác giả:
- Hà Phước Vũ - Lớp 10A5, trường THPT Chuyên Lê Quý Đôn, Đà Nẵng.

## I. Giới thiệu.
Lý thuyết số trong CP luôn xoay quanh các khái niệm toán học mà phần lớn chúng ta đều biết. Trong số đó, Số nguyên tố và các vấn đề liên quan đến nó luôn hiện hữu quanh chúng ta và xuất hiện trong một số bài tập CP.

Trong bài viết này, chúng ta sẽ đi sâu vào một vài vấn đề kinh điển về Số nguyên tố.
## II. Các vấn đề kinh điển về Số nguyên tố.
### 1. Tính nguyên tố.
#### 1. Thuật toán ngây thơ.
Để kiểm tra một số nguyên dương $n$ có phải số nguyên tố hay không, ta sẽ nghĩ ngay đến kiểm tra $n$ có ước trong đoạn $[2, n-1]$ hay không. Nếu không thì $n$ rõ ràng là một số nguyên tố và ngược lại. Khi đó, chúng ta sẽ có một cách giải với độ phức tạp thời gian là $O(n)$ như sau:

// ll là long long
bool IsPrime(ll n) {
    for (ll i = 2; i < n; i++) {
        if (n%i == 0) return 0;
    }
    return 1;
}

#### 2. Thuật toán tối ưu.
Ta có một nhận xét như sau:
- Nếu như $i$ là ước của $n$ thì $\frac{n}{i}$ cũng là ước của $n$.

Nhận xét trên cho ta biết rằng $n$ sẽ luôn luôn có một ước trong đoạn $[1, \sqrt{n}]$. Vì vậy, ta chỉ cần kiểm tra $n$ có ước trong đoạn $[2, \sqrt{n}]$ thay vì $[2, n-1]$ như trên. Khi đó, chúng ta sẽ có một cách giải với độ phức tạp thời gian là $O(\sqrt{n})$ như sau:

// ll là long long
bool IsPrime(ll n) {
    if (n < 2) return 0;
    for (ll i = 2; i*i <= n; i++) {
        if (n%i == 0) return 0;
    }
    return 1;
}

Tiếp tục, ta còn có một định lý như sau:
- Mọi số nguyên tố lớn hơn $3$ đều có dạng $6\times n+1$ hoặc $6\times n-1$.

Từ nhận xét trên, trước hết ta sẽ kiểm tra $2$ hoặc $3$ có phải là ước của $n$ hay không. Sau đó với mỗi $i$ từ $5$ đến $\sqrt{n}$, ta sẽ kiểm tra $i$ hoặc $i+2$ có phải ước của $n$ hay không. Vì ta đang áp dụng định lý trên nên mỗi vòng lặp, $i$ sẽ nhảy lên $6$ đơn vị. Khi đó, chúng ta sẽ có một cách giải với độ phức tạp thời gian là $O(\frac{\sqrt{n}}{6})$ như sau:

// ll là long long
bool IsPrime(ll n) {
    if (n < 2) return 0;
    else if (n < 4) return 1;
    else if (min(n%2, n%3) == 0) return 0;
    for (ll i = 5; i*i <= n; i += 6) {
        if (min(n%i, n%(i+2)) == 0) return 0;
	}
    return 1;
}

Qua những giải pháp trên, ta có thể thấy đây là một cách kiểm tra **rất** tối ưu với mọi số nguyên dương $n$ thỏa mãn $1 \le n \le 10^{16}$.

**Bonus:** Ngoài ra, ta có thể thấy rằng trừ $2$ thì mọi số nguyên tố đều là số lẻ. Vì vậy, ta có thể kiểm tra $2$ có phải ước của $n$ không và kiểm tra $n$ có ước trong đoạn $[3, \sqrt{n}]$ hay không sử dụng bước nhảy $2$.
#### 3. Giải pháp xác suất.
Phần lớn chúng ta đều biết đến [định lý Fermat](https://vi.wikipedia.org/wiki/%C4%90%E1%BB%8Bnh_l%C3%BD_nh%E1%BB%8F_Fermat), được phát biểu như sau:
- Nếu $p$ là số nguyên tố và $a$ là một số nguyên không phải là ước của $p$ thì $a^{p-1}-1$ là bội của $p$.

Từ định lý trên, chúng ta sẽ có một cách giải với độ phức tạp thời gian là $O(log_2n)$ bởi ta tính $a^{p-1}$ bằng lũy thừa nhị phân.

// ll là long long
ll expo(ll a, ll b, ll m) {
    ll res = 1;
    while (b > 0) {
        if (b&1) (ans *= a) %= m;
        (a *= a) %= m, b >>= 1;
    }
    return res;
}
bool IsPrime(ll n) {
    if (n%2 == 0) return 0;
    return expo(2, n-1, n) == 1;
}

Tuy nhiên, định lý Fermat không hoàn toàn đúng trong mọi trường hợp. Tồn tại những số nguyên dương là hợp số nhưng lại thỏa mãn định lý Fermat, và chúng được gọi là số Carmichael như $341$ hay $101101$. Với những số này, định lý Fermat chỉ đúng khi bạn chọn $a$ trong code của bạn là ước của các số đó. Tuy nhiên, điều này là hoàn toàn không thể khi số lượng số Carmichael là không hề ít.

Ngoài định lý trên ra, chúng ta còn có [định lý Wilson](https://vi.wikipedia.org/wiki/%C4%90%E1%BB%8Bnh_l%C3%BD_Wilson), được phát biểu như sau:
- Nếu $p$ là số nguyên tố thì $(p-1)! \equiv p-1$ $(mod$ $p)$.

Từ định lý trên, chúng ta sẽ có một cách giải với độ phức tạp thời gian tương tự như thuật toán ngây thơ là $O(n)$.

// ll là long long
bool IsPrime(ll n) {
    ll fac = 1;
    for (ll i = 2; i < n; i++) {
        (fac *= i) %= n;
    }
    return fac == n-1;
}

Ngoài cách kiểm tra như trên, ta vẫn có thể tối ưu với độ phức tạp là $O(\sqrt{n}\times log_2{\sqrt{n}})$ bằng cách sử dụng FFT để tính $n!$ nhanh được đề cập tại [bài viết này](https://fredrikj.net/blog/2012/03/factorials-mod-n-and-wilsons-theorem/).

Ngoài $2$ cách khá lạ ở bên trên, chúng ta còn có một cách khá quen thuộc và rất nhanh với tính đúng đắn cao là [Phương pháp kiểm tra tính nguyên tố Miller Rabin](https://vietcodes.github.io/algo/miller). Chúng ta sẽ có một cách giải với độ phức tạp thời gian là $O(k\times log_2n)$ với $k$ là số lần thử.

// ll là long long
int pr[] = {}; // Có thể thay đổi.
ll expo(ll a, ll b, ll m) {
    ll res = 1;
    while (b > 0) {
        if (b&1) (ans *= a) %= m;
        (a *= a) %= m, b >>= 1;
    }
    return res;
}
bool IsPrime(ll n) {
    if (n < 2) return 0;
    else if (n < 4) return 1;
    else if (n%2 == 0) return 0;
    ll d = n-1; int s = 0; 
    while (d%2 == 0) d /= 2, s++;
    for (auto a : pr) {
        if (n == a) return 1;
        ll p = expo(a, d, n);
        for (int i = 0; i < s-1; i++) {
            (p *= p) %= n;
            if (p == n-1) break;
        }
        if (p != n-1) return 0;
    }
    return 1;
}

Với cách trên, nếu số lượng số nguyên tố bạn thử càng lớn thì độ chính xác sẽ càng cao. Thay vì bạn đặt $a$ là một số nguyên tố, bạn cũng có thể cho $a$ là một số nguyên dương ngẫu nhiên nào đó.
#### 4. Luyện tập.
Một số bài tập về kiểm tra tính nguyên tố.
- [TLEOJ - Số Sigma](https://tleoj.edu.vn/problem/34c).
- [TLEOJ - Số độc lạ](https://tleoj.edu.vn/problem/53c).
### 2. Sàng Eratos và ứng dụng.
#### 1. Sàng Eratos.
Để lấy những số nguyên tố trong đoạn $[1, n]$, ta có thể duyệt qua các số từ $1$ đến $n$ và kiểm tra bằng cách $O(\frac{\sqrt{n}}{6})$ hoặc $O(k\times log_2n)$.

Ngoài cách ngây thơ ở trên, chúng ta có thể sử dụng [Sàng nguyên tố Eratosthenes](https://vi.wikipedia.org/wiki/S%C3%A0ng_Eratosthenes). Tuy nhiên, ta có thể tối ưu một chút ý tưởng trên với một nhận xét đã được đề cập ở trên:
- Nếu như $i$ là ước của $n$ thì $\frac{n}{i}$ cũng là ước của $n$.

Từ nhận xét trên, ta dễ dàng thấy nếu $i$ không phải là số nguyên tố thì $i$ chắc chắn sẽ có một ước nguyên tố trong đoạn $[2, \sqrt{i}]$. Khi đó trong phần `Sieve`, $i$ chỉ cần duyệt tới $\sqrt{n}$. Dựa vào ý tưởng trên, chúng ta sẽ có một cách giải với độ phức tạp thời gian xấp xỉ $O(n \times log_2log_2\sqrt{n})$.

bool f[lim+5]; 
void Sieve(int n) {
    f[0] = f[1] = 1;
    for (int i = 2; i*i <= n; i++) {
        if (f[i] == 0) {
            for (int j = 2; i*j <= n; j++) {
                f[i*j] = 1;
            }
        }
    }
    return;
}

Ngoài ra thì như đã đề cập ở trên, ta còn có một định lý như sau:
- Mọi số nguyên tố lớn hơn $3$ đều có dạng $6\times n+1$ hoặc $6\times n-1$.

Từ nhận xét trên, ta có thể cải tiến sàng Eratos như sau:
- Đánh dấu các số $i$ có dạng $2\times j$ $(2 \le j \le \frac{n}{2})$ và $6\times j+3$ $(1 \le j \le \frac{n}{6})$.
- Duyệt $i$ từ $5$ đến $\sqrt{n}$ với bước nhảy $6$ và thực hiện phép đánh dấu với $i$ và $i+2$ như sàng Eratos thông thường nếu $f[i] = 0$ và $f[i+2] = 0$.

Dựa vào ý tưởng trên, chúng ta sẽ có một cách giải với độ phức tạp thời gian xấp xỉ $O(\frac{n \times log_2log_2\sqrt{n}}{6})$.

bool f[lim+5]; 
void Sieve(int n) {
    f[0] = f[1] = 1;
    for (int i = 4; i <= n; i += 2) f[i] = 1;
    for (int i = 9; i <= n; i += 6) f[i] = 1;
    for (int i = 5; i*i <= n; i += 6) {
        if (f[i] == 0) {
            for (int j = 2; i*j <= n; j++) {
                f[i*j] = 1;
            }
        }
        if (f[i+2] == 0) {
            for (int j = 2; (i+2)*j <= n; j++) {
                f[(i+2)*j] = 1;
            }
        }
    }
    return;
}

Với Sàng Eratos trên đoạn, bạn có thể áp dụng tương tự.
#### 2. Ứng dụng.
Nếu hiểu được bản chất của Sàng Eratos, bạn còn có thể nghĩ ra những biến thể của Sàng Eratos. Một số biến thể phổ biến mà phần lớn chúng ta sẽ biết là Sàng thừa số nguyên tố nhỏ nhất, Sàng ước, Sàng Phi hàm Euler, Sàng Square-free, $...$ Ngoài ra, ta cũng có thể sử dụng Sàng để tối ưu một thuật toán nào đấy.

Và với các loại biến thể của Sàng Eratos trên, ta sẽ luôn có một công thức chung như sau:
- Xác định $f[i]$ có ý nghĩa gì, làm sao để dựng $f[i]$.
- Nếu thỏa mãn tính chất của cách xây dựng Sàng Eratos, cài đặt như Sàng Eratos với bước nhảy $6$.

Dưới đây sẽ là code mẫu cho công thức chung trên.
- Code mẫu $1$: Chỉ duy nhất số nguyên tố.

Data f[lim+5]; // Data là một kiểu dữ liệu tùy chỉnh.
void Sieve(int n) {
    f[0] = f[1] = ...;
    for (int i = 4; i <= n; i += 2) f[i] = ...; // Tùy chỉnh.
    for (int i = 9; i <= n; i += 6) f[i] = ...; // Tùy chỉnh.
    for (int i = 5; i*i <= n; i += 6) {
        if (f[i] == ...) { // Tùy chỉnh.
            for (int j = 2; i*j <= n; j++) {
                f[i*j] = ... // Tùy chỉnh.
            }
        }
        if (f[i+2] == ...) { // Tùy chỉnh.
            for (int j = 2; (i+2)*j <= n; j++) {
                f[(i+2)*j] = ... // Tùy chỉnh.
            }
        }
    }
    return;
}

- Code mẫu $2$: Không quan trọng tính nguyên tố.

Data f[lim+5]; // Data là một kiểu dữ liệu tùy chỉnh.
void Sieve(int n) {
    for (int i = 1; i <= n; i++) {
        if (f[i] == ...) { // Tùy chỉnh.
            for (int j = 1; i*j <= n; j++) {
                f[i*j] = ... // Tùy chỉnh.
            }
        }
    }
    return;
}

**Bonus:** Dựa vào tính chất của thừa số nguyên tố nhỏ nhất, bạn có thể tối ưu Sàng Eratosthenes xuống độ phức tạp $O(n)$. Kết hợp với bước nhảy $6$, độ phức tạp thời gian khi đó sẽ là $O(\frac{n}{6})$.
#### 3. Luyện tập.
Một số bài tập về Sàng Eratos và biến thể của chúng.
- [CSES - Counting Divisors](https://cses.fi/problemset/task/1713).
- [CSES - Common Divisors](https://cses.fi/problemset/task/1081).
- [LQDOJ - Sàng nguyên tố](https://lqdoj.edu.vn/problem/sieve).
- [TLEOJ - Đếm số nguyên tố trên đoạn](https://tleoj.edu.vn/problem/37b).
- [TLEOJ - Tích chính phương](https://tleoj.edu.vn/problem/70a).
- [TLEOJ - Tích ước chung lớn nhất](https://tleoj.edu.vn/problem/3f).
- [TLEOJ - Cặp số nguyên tố cùng nhau](https://tleoj.edu.vn/problem/22c).

Số lượng bài mình đề xuất ở đây khá ít bởi mình rất lười. Các bạn có thể tự tìm kiếm ở trên các trình chấm online.
### 3. Phân tích thừa số nguyên tố.
#### 1. Thuật toán ngây thơ.
Để phân tích $n$ thành thừa số nguyên tố, ta duyệt qua các số nguyên dương $p$ trong đoạn $[2, n]$. Khi gặp $p$ là ước của $n$, ta có thể chắc chắn rằng $p$ sẽ là ước nguyên tố của $n$ dựa vào tính chất của Sàng Eratos. Sau đó, ta sẽ loại bỏ hết thừa số $p$ trong $n$ và tiếp tục. Khi đó, chúng ta sẽ có cách giải với độ phức tạp thời gian là $O(n)$.

// ll là long long
map<ll, ll> PrimeFactor(ll n) {
    ll tmp = n; map<ll, ll> cnt;
    for (ll i = 2; i < tmp; i++) {
        if (n%i == 0) {
            while (n%i == 0) {
                n /= i, cnt[i]++;
            }
        }
    }
    return cnt;
}

#### 2. Thuật toán tối ưu.
Vẫn là nhận xét quen thuộc:
- Nếu $i$ là ước của $n$ thì $\frac{n}{i}$ là ước của $n$.

Từ nhận xét trên, ta sẽ chỉ kiểm tra các ước nguyên tố $p$ trong đoạn $[2, \sqrt{n}]$. Nếu như sau khi loại bỏ sự xuất hiện của mọi ước nguyên tố $p$ trong $n$ và $n > 1$, khi đó ta chắc chắn rằng $n$ khi đó sẽ là số nguyên tố. Ta có thể chứng minh như sau:
- Trong trường hợp $n > 1$ khi đã loại bỏ như trên, nếu $n$ không phải số nguyên tố thì $n = p\times q$ với $p, q \in N^{*}$.
- Với nhận xét quen thuộc ở trên, $p$ hoặc $q$ phải thỏa mãn không lớn hơn $\sqrt{n}$. Bởi vì $n$ sau khi loại bỏ sự xuất hiện của mọi ước nguyên tố $p$ thì $\sqrt{n}$ lúc đó sẽ nhỏ hơn $\sqrt{n}$ ban đầu rất nhiều. Vì vậy $p, q$ sẽ nằm trong đoạn $\sqrt{n}$ ban đầu. Khi đó $n = 1$.
- Từ $2$ điều trên, ta thấy rằng $n = 1$ và $n > 1$ là hoàn toàn vô lý. Vì vậy, $n$ sẽ là số nguyên tố.

Khi đó, chúng ta sẽ có cách giải với độ phức tạp thời gian là $O(\sqrt{n})$.

// ll là long long
map<ll, ll> PrimeFactor(ll n) {
    map<ll, ll> cnt;
    for (ll i = 2; i*i <= n; i++) {
        if (n%i == 0) {
            while (n%i == 0) {
                n /= i, cnt[i]++;
            }
        }
    }
    if (n > 1) cnt[n]++;
    return cnt;
}

Vẫn là định lý quen thuộc:
- Mọi số nguyên tố lớn hơn $3$ đều có dạng $6\times n+1$ hoặc $6\times n-1$.

Khi đó, ta sẽ cài đặt tương tự như cách cài đặt kiểm tra tính nguyên tố với bước nhảy $6$. Và độ phức tạp thời gian của cách giải khi đó là $O(\frac{\sqrt{n}}{6})$.

// ll là long long
map<ll, ll> PrimeFactor(ll n) {
    map<ll, ll> cnt;
    if (n%2 == 0) {
        while (n%2 == 0) {
            n /= 2, cnt[2]++;	
        }	
    }
    if (n%3 == 0) {
        while (n%3 == 0) {
            n /= 3, cnt[3]++;	
        }	
    }
    for (ll i = 5; i*i <= n; i += 6) {
        if (n%i == 0) {
            while (n%i == 0) {
                n /= i, cnt[i]++;
            }
        }
        if (n%(i+2) == 0) {
            while (n%(i+2) == 0) {
                n /= (i+2), cnt[i+2]++;
            }
        }
    }
    if (n > 1) cnt[n]++;
    return cnt;
}

Các cách trên sẽ cực kì nhanh nếu như mỗi lần nhảy, ta sẽ nhảy đến chính xác ước nguyên tố của $n$ lúc đó. Giả sử bước đấy là $O(1)$ thì tổng độ phức tạp thời gian cho việc phân tích thừa số nguyên tố sẽ là $O(log_2n)$. Để làm điều đó, ta có thể sử dụng Sàng thừa số nguyên tố nhỏ nhất. Khi đó, chúng ta có cách giải với độ phức tạp thời gian là $O(\frac{n \times log_2log_2n}{6})$ cho phần Sàng thừa số nguyên tố nhỏ nhất và $O(log_2n)$ cho phần phân tích thừa số nguyên tố.

int f[lim+5]; 
void Sieve(int n) {
    f[0] = f[1] = 1;
    for (int i = 2; i <= n; i += 2) f[i] = 2;
    for (int i = 3; i <= n; i += 6) f[i] = 3;
    for (int i = 5; i*i <= n; i += 6) {
        if (f[i] == 0) { 
            for (int j = 2; i*j <= n; j++) {
                if (f[i*j] == i*j) f[i*j] = i;
            }
        }
        if (f[i+2] == 0) {
            for (int j = 2; (i+2)*j <= n; j++) {
                if (f[(i+2)*j] == (i+2)*j) f[(i+2)*j] = i+2;
            }
        }
    }
    return;
}
map<int, int> PrimeFactor(int n) {
    map<ll, ll> cnt;
    while (n > 1) {
        int p = sang[n];
        while (n%p == 0) {
            n /= p, cnt[p]++;
        }
    }
    return cnt;
}

Hạn chế của cách trên là chỉ áp dụng được với $1 \le n \le 10^7$, tuy nhiên nếu số lượng số $n$ cần phân tích lên đến $10^5$ thì đây là một cách rất nhanh.

Với những số nguyên dương $n$ lớn mà ta vẫn muốn áp dụng ý tưởng nhảy tới ước nguyên tố trong $O(1)$, ta có thể sử dụng Sàng Eratos để lấy các số nguyên tố trong đoạn $O(\sqrt{n})$. Sau đó phân tích thừa số nguyên tố $n$ bằng cách duyệt qua các số nguyên tố trong đoạn $[2, \sqrt{n}]$. Khi đó, chúng ta có cách giải với độ phức tạp thời gian là $O(pi(\sqrt{n}))$, bỏ qua phần Sàng Eratos.

bool f[lim+5]; vector<int> pr;
void Sieve(ll n) {
    // Tự code.
}
map<ll, ll> PrimeFactor(ll n) {
    Sieve((ll)sqrt(n));
    map<ll, ll> cnt;
    for (auto i : pr) {
        if (i*i > n) break;
        else if (n%i == 0) {
            while (n%i == 0) {
                n /= i, cnt[i]++;
            }
        }
    }
    if (n > 1) cnt[n]++;
    return cnt;
}

Nếu như xử lý nhiều truy vấn thì `Sieve()` có thể xử lý trước khi nhập các truy vấn với $n = \sqrt{lim}$ ($lim$ là giới hạn của $n$ mà đề bài cho).
#### 3. Thuật toán Pollard's Rho.
Ngoài $2$ cách trên, ta còn có thể sử dụng thuật toán Pollard's Rho để phân tích thừa số nguyên tố trong $O(\sqrt[4]{n}\times log_2n)$.

Bạn có thể xem code tham khảo về cách trên tại [đây](https://github.com/ngthanhtrung23/ACM_Notebook_new/blob/master/Math/NumberTheory/Pollard_factorize.h) và ý tưởng tại [đây](https://www.geeksforgeeks.org/pollards-rho-algorithm-prime-factorization/).
#### 4. Luyện tập.
- [CSES - Counting Divisors](https://cses.fi/problemset/task/1713).
- [TLEOJ - Tình bạn](https://tleoj.edu.vn/problem/friendship).

Số lượng bài mình đề xuất ở đây khá ít bởi mình rất lười. Các bạn có thể tự tìm kiếm ở trên các trình chấm online.
## III. Tổng kết.
Đây là một bài viết được viết với mục đích giải trí. Tuy nhiên, nó có thể khai sáng tâm trí của bạn khi nó cho bạn thấy một cái nhìn sâu về Số nguyên tố mà có lẽ bạn cũng không nghĩ đến hay tiếp cận trên Internet.

Một số nguồn nên tham khảo:
- [Prime Sieving - SPyofgame](https://hackmd.io/@spyofgame/sieve).

Hy vọng bài viết này giúp ích cho bạn một phần nào. Chúc các bạn một ngày vui vẻ.