• Hàm kiểm tra số nguyên tố
  • Cải tiến
• Sàng nguyên tố
• Phân tích thừa số nguyên tố
  • Số ước số và tổng các ước số
    • Số ước số
    • Tổng các ước số
• Phi hàm Euler

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\ne 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

$[2;\sqrt{n}]$:

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;
}

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 \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] == true) {
            for(int j = i; i * j <= MAXN; ++j) // loại tất cả bội của j 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 lpd[MAXN + 1]; // least prime divisor

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

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 \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 lpd đã tính ở trên:

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

Ta mất

$O(n\log \log n)$ để sàng lpd 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 \log n+q\log n)$.

Số ước số và tổng các ước số

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$
$⋮$	$⋮$	$⋮$	$\ddots$	$⋮$
${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à:

$$\begin{array}{c}(1+p_1+{p_1}^2+\cdots +{p_1}^{c_1})+(p_2+p_1\cdot p_2+{p_1}^2\cdot p_2+\cdots +{p_1}^{c_1}\cdot p_2)+\\ ({p_2}^2+p_1\cdot {p_2}^2+{p_1}^2\cdot {p_2}^2+\cdots +{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}+\cdots +{p_1}^{c_1}\cdot {p_2}^{c_2})\\ =(1+p_1+{p_1}^2+\cdots +{p_1}^{c_1})+p_2\cdot (1+p_1+{p_1}^2+\cdots +{p_1}^{c_1})+\\ {p_2}^2(1+p_1+{p_1}^2+\cdots +{p_1}^{c_1})+...+{p_2}^{c_2}\cdot (1+p_1+{p_1}^2+\cdots +{p_1}^{c_1})\\ =(1+p_1+{p_1}^2+\cdots +{p_1}^{c_1})\cdot (1+p_2+{p_2}^2+\cdots +{p_2}^{c_2})\end{array}$$

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+\cdots +{p_1}^{c_1})\cdot (1+p_2+{p_2}^2+\cdots +{p_2}^{c_2})...(1+p_m+{p_m}^2+\cdots +{p_m}^{c_m})$

int divisors_sum(int n) {
    int 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;
}

Phi hàm Euler

Phi hàm Euler

$\varphi (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

$⟺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}$,

$\varphi (n)=n\cdot (1-\frac{1}{p_1})\cdot (1-\frac{1}{p_2})...(1-\frac{1}{p_m})$

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

$\varphi (i)$ cho mọi

$i$ từ

$1$ tới

$n$:

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;
        }
    }
}