[TOC]

## Hàm kiểm tra số nguyên tố
Ta có thể thấy rằng mọi hợp số n đều có ít nhất 2 ước $i$ và $j$ ($i \le j$, $i$, $j \neq 1, n$) sao cho $i \cdot j = n$. Vậy chỉ cần kiểm tra tất cả các $i$, và vì $i$ lớn nhất có thể là $\sqrt n$ nên ta chỉ cần kiểm tra các số trong khoảng $\left[2; \sqrt n\right]$:

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

### Cải tiến
Một tính chất khác có thể thấy là các số nguyên tố $\ge 5$ đều có dạng $6k + 1$ hay $6k - 1$, vậy ta cũng sẽ bắt đầu kiểm tra $i$ từ $5$, xét xem $n$ có chia hết cho $i$ hay $i+2$ hay không, và tăng $i$ lên $6$ sau mỗi lần lặp:

bool is_prime(int n) {
    if(n <= 1)
        return false;
    if(n == 2 || n == 3)
        return true;
    if(n % 2 == 0 || n % 3 == 0)
        return false;
    for(int i = 5; i * i <= n; i += 6) {
        if(n % i == 0 || n % (i + 2) == 0)
            return false;
    }
    return true;
}

<br>

## Sàng nguyên tố
Sàng nguyên tố (sieve of Eratosthenes) là một thuật toán kiểm tra số nguyên tố trong đoạn $[1; n]$ với độ phức tạp $O(n \log n)$.
**Ý tưởng**: Ta sẽ loại bỏ bội của các số nguyên tố dần dần (đã là bội của một số thì là hợp số). Ta sẽ bắt đầu từ $2$:
* Bước 1: Kiểm tra số $i$ hiện tại đã bị đánh dấu là hợp số chưa, nếu rồi ta bỏ qua, tìm $i$ tiếp theo chưa bị đánh dấu khỏi số nguyên tố.
* Bước 2: $i$ hiện tại là số nguyên tố. Ta lần lượt đánh dấu các bội của $i$ ra khỏi số nguyên tố. Sau đó tăng $i$ lên 1
* Tiếp tục lặp lại 2 bước trên tới $i \le \sqrt n$

Như ảnh bên dưới, các số được tô màu đậm sẽ là các số nguyên tố, những số tô màu nhạt tương ứng sẽ là bội của số nguyên tố ấy.


const int MAXN = 1e7;

bool is_prime[MAXN + 1];

void sieve() {
    for(int i = 2; i <= MAXN; ++i)
        is_prime[i] = true; // mặc định mọi số đều là nguyên tố
    for(int i = 2; i * i <= MAXN; ++i) {
        if(is_prime[i] == false) continue;
        for(int j = 2; i * j <= MAXN; ++j) // loại tất cả bội của i khỏi nguyên tố
            is_prime[i * j] = false;
    }
}

Bên cạnh đó, ta cũng có thể tích hợp tìm ước nguyên tố nhỏ nhất vào sàng nguyên tố:

const int MAXN = 1e7;

int spf[MAXN + 1]; // smallest prime factor

void sieve() {
    for(int i = 2; i <= MAXN; ++i) {
        if(spf[i] != 0) continue;
        // spf[i] = 0 => i là số nguyên tố
        for(int j = 1; i * j <= MAXN; ++j) {
            if(spf[i * j] == 0) // spf[i * j] = 0 => i sẽ là ước nguyên tố nhỏ nhất của i * j
                spf[i * j] = i;
        }
    }
}

<br>

## Phân tích thừa số nguyên tố
Ta có thể phân tích thừa số nguyên tố với độ phức tạp $O(\sqrt n)$:

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

Thuật toán trên đảm bảo *prime_factors* sẽ chỉ chứa số nguyên tố. Giả sử $n$ có một ước hợp số là $x$ với $x = {p_1}^{c_1} \cdot {p_2}^{c_2} ... {p_m}^{c_m}$ với $p_i$ là một ước nguyên tố của $x$, $c_i$ là số mũ của $p_i$ trong $x$. Khi này, vì các $p_i < x$, $n$ sẽ chia cho các $p_i$ trước, và sau khi chia hết cho các $p_i$ thì $n$ hiện tại sẽ không còn chia hết cho $x$ nữa, vì thế *prime_factors* sẽ chỉ chứa các ước nguyên tố.
Khi có $q$ truy vấn, độ phức tạp sẽ là $O(q \cdot \sqrt n)$.

Có một cách cải tiến xử lí truy vấn từ $O(q \cdot \sqrt n)$ thành $O(n \log n + q \log n)$, với $q$ và $n$ càng lớn thì sẽ càng hiệu quả hơn. Ta sẽ dùng mảng *spf* đã tính ở trên:

vector<int> prime_factorize(int n) {
    vector<int> prime_factors;
    while(n > 1) {
        prime_factors.push_back(spf[n]);
        n /= spf[n];
    }
    return prime_factors;
}

Ta mất $O(n \log n)$ để sàng *spf* preprocess ở đầu, sau đó với mỗi truy vấn thì hàm phân tích thừa số nguyên tố mất $O(\log n)$, vì thế tổng độ phức tạp là $O(n \log n + q \log n)$.

### Số ước số và tổng các ước số
Kí hiệu:
Số ước số của $n$: $d(n)$
Tổng các ước số của $n$: $\sigma(n)$

#### Số ước số
Xét số $x$ có dạng $p^c$ với $p$ là một số nguyên tố và $c$ là số mũ của số nguyên tố ấy. Có thể thấy $x$ sẽ có $c+1$ ước số: $1, \, p, \, p^2, \, \dots, \, p^c$ ($1$ là $p^0$)

Xét số $x$ có dạng ${p_1}^{c_1} \cdot {p_2}^{c_2}$. Các ước của $x$ là:

| $1$ | $p_1$ | ${p_1}^2$ | $\dots$ | ${p_1}^{c_1}$ |
|:-------------:|:-----------------------:|:---------------------------:| -------- |:-------------------------------:|
| $p_2$ | $p_1 \cdot p_2$ | ${p_1}^2 \cdot p_2$ | $\dots$ | ${p_1}^{c_1} \cdot p_2$ |
| ${p_2}^2$ | $p_1 \cdot {p_2}^2$ | ${p_1}^2 \cdot {p_2}^2$ | $\dots$ | ${p_1}^{c_1} \cdot {p_2}^2$ |
| $\vdots$ | $\vdots$ | $\vdots$ | $\ddots$ | $\vdots$ |
| ${p_2}^{c_2}$ | $p_1 \cdot {p_2}^{c_2}$ | ${p_1}^2 \cdot {p_2}^{c_2}$ | $\dots$ | ${p_1}^{c_1} \cdot {p_2}^{c_2}$ |

Dễ có thể thấy $d(x) = (c_1+1) \cdot (c_2+1)$.

Tổng quát hơn, $d(x)$ của $x = {p_1}^{c_1} \cdot {p_2}^{c_2} \cdot {p_3}^{c_3} ... {p_m}^{c_m}$ là $(c_1+1) \cdot (c_2+1) \cdot (c_3+1) ... (c_m+1)$

int divisors_count(int n) {
    int total = 1;
    for(int i = 2; i * i <= n; ++i) {
        int cnt = 0;
        while(n % i == 0) {
            ++cnt;
            n /= i;
        }
        total *= cnt + 1;
    }
    if(n > 1) total *= 2;
    return total;
}

#### Tổng các ước số
Tương tự với số các ước số, ta cũng có các ước như bảng trên.
Vậy tổng sẽ là: $$\displaylines{(1 + p_1 + {p_1}^2 + \dots + {p_1}^{c_1}) + (p_2 + p_1 \cdot p_2 + {p_1}^2 \cdot p_2 + \dots + {p_1}^{c_1} \cdot p_2) + \\ ({p_2}^2 + p_1 \cdot {p_2}^2 + {p_1}^2 \cdot {p_2}^2 + \dots + {p_1}^{c_1} \cdot {p_2}^2) + ... + ({p_2}^{c_2} + p_1 \cdot {p_2}^{c_2} + {p_1}^2 \cdot {p_2}^{c_2} + \dots + {p_1}^{c_1} \cdot {p_2}^{c_2})
\\ = (1 + p_1 + {p_1}^2 + \dots + {p_1}^{c_1}) + p_2 \cdot (1 + p_1 + {p_1}^2 + \dots + {p_1}^{c_1}) + \\ {p_2}^2(1 + p_1 + {p_1}^2 + \dots + {p_1}^{c_1}) + ... + {p_2}^{c_2} \cdot (1 + p_1 + {p_1}^2 + \dots + {p_1}^{c_1})
\\ = (1 + p_1 + {p_1}^2 + \dots + {p_1}^{c_1}) \cdot (1 + p_2 + {p_2}^2 + \dots + {p_2}^{c_2})}$$

Tổng quát hơn, $\sigma(x)$ của $x = {p_1}^{c_1} \cdot {p_2}^{c_2} \cdot {p_3}^{c_3} ... {p_m}^{c_m}$ là $(1 + p_1 + {p_1}^2 + \dots + {p_1}^{c_1}) \cdot (1 + p_2 + {p_2}^2 + \dots + {p_2}^{c_2}) ... (1 + p_m + {p_m}^2 + \dots + {p_m}^{c_m})$

int divisors_sum(int n) {
    long long total = 1;
    for(int i = 2; i * i <= n; ++i) {
        int p = 1, sum = 1;
        while(n % i == 0) {
            p *= i;
            sum += p;
            n /= i;
        }
        total *= sum;
    }
    if(n > 1) total *= (1 + n);
    return total;
}

<br>

## Phi hàm Euler
Phi hàm Euler $\phi(n)$ cho ta biết có bao nhiêu số từ $1$ đến $n$ là số nguyên tố cùng nhau với $n$ ($a$ và $b$ nguyên tố cùng nhau $\iff \gcd(a, b) = 1$)

Công thức: với $n = {p_1}^{c_1} \cdot {p_2}^{c_2} \cdot \; ... \, \cdot {p_m}^{c_m}$, $\phi(n) = n \cdot \left(1 - {1 \over p_1}\right) \cdot \left(1 - {1 \over p_2}\right) ... \left(1 - {1 \over p_m}\right)$

int phi(int n) {
    int res = n;
    for(int i = 2; i * i <= n; ++i) {
        if(n % i == 0) {
            while(n % i == 0) n /= i;
            res -= res / i;
        }
    }
    if(n > 1) res -= res / n;
    return res;
}

Tính $\phi(i)$ cho mọi $i$ từ $1$ tới $n$ bằng cách dùng sàng:

int phi_sieve() {
    for(int i = 0; i <= MAXN; ++i)
        phi[i] = i;
    for(int i = 2; i <= MAXN; ++i) {
        if(phi[i] == i) {
            for(int j = 1; i * j <= MAXN; ++j)
                phi[i * j] -= phi[i * j] / i;
        }
    }
}