---
title: '2SG TIN [Số học]'
disqus: hackmd
---

**Chuyên đề số học - Toán trong Tin**
===
✍️ ***Author: 2School Guideline***

## **Table of Contents**
[TOC]

---

-----
## **Lời mở đầu**
Hôm nay có một bạn chuyên Toán hỏi ban Tin 2SG:
:::warning
##### - Các bạn chuyên Tin có cần biết Toán không?
:::
Ban Tin của 2SG chỉ mỉm cười và đáp ngắn gọn như sau:
:::success
##### - Chim thiếu ăn chim tìm con sâu. Tin thiếu Toán, Tin sầu con tim...!
:::
:::info
#### Bài viết này sẽ giúp các bạn thấy rõ hơn vẻ đẹp của sự kết hợp giữa Tin học và Toán học cũng như giới thiệu đến các bạn một vài chuyên đề số học cơ bản như sau:
:::

| Số nguyên tố |
| -------- |
| **Sàng Eratosthenes** |
| **Ước chung lớn nhất và bội chung nhỏ nhất** |
| **Phân tích số nguyên** |

## **Số nguyên tố**
---
### 1. Khái niệm
#### Số nguyên tố là số nguyên lớn hơn 1 và có đúng 2 ước là 1 và chính nó.

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

#### Nhận xét:
- Số 2 là số nguyên tố chẵn duy nhất.
- Cũng như tính chất của số nguyên dương, chúng ta chỉ tìm thấy số nguyên tố nhỏ nhất chứ không thể tìm thấy số nguyên tố lớn nhất.
:::info
**Từ định nghĩa trên, chúng ta sẽ có một vài thuật toán kiểm tra 1 số nguyên N có phải là nguyên tố hay không.**
:::
### 2. Thuật toán kiểm tra số nguyên tố
### A. Thuật toán "mầm non"
Xét theo định nghĩa về số nguyên tố, ta có thể chạy vòng for từ $1$ đến $N$ để đếm số lượng ước của số nguyên dương $N$. Nếu $N$ có 2 ước thì $N$ là số nguyên tố, ngược lại $N$ không là số nguyên tố.
#### Nhận xét chung
:::info
- Nếu $N < 2$ thì $N$ không là số nguyên tố.
- Nếu $N \ge 2$ và $N$ có 2 ước thì $N$ là số nguyên tố.
:::

#### Code mẫu:

#include <bits/stdc++.h>
using namespace std;
int n;
bool check(int x) {
    if (x < 2) {
        return false;
    }
    int dem = 0;
    for (int i=1;i<=n;i++) {
        if (n%i == 0) {
            ++dem;
        }
    }
    if (dem == 2) {
        return true;
    } else {
        return false;
    }
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    if (check(n)) {
        cout << "TRUE";
    } else {
        cout << "FALSE";
    }
}

#### Độ phức tạp của thuật toán:
:::info
Độ 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$.
:::

### B. Thuật toán “trưởng thành”
#### **Giải thích:**
**Xét số nguyên tố p**
- Nếu $p$ lớn hơn $sqrt(n)$, và chúng ta xem xét bất kỳ bội số nào của $p$ lớn hơn $sqrt(n)$, ví dụ như $2p$, $3$, ..., thì mỗi bội số đó sẽ vượt quá giới hạn $n$ và không thể là số nguyên tố.
- Điều này là do nếu $p$ lớn hơn căn bậc hai của $n$, thì $p * p$ cũng sẽ lớn hơn $n$.
- Vì vậy, tất cả các bội số của $p$ lớn hơn $sqrt(n)$ sẽ vượt quá giới hạn $n$ và không cần phải kiểm tra nữa.

#### **Chứng minh:**
:::info
**● Giả sử n là hợp số ⟹ ta có thể biểu diễn n = a × b với a, b là ước dương
của n
● Giả sử: 1 ≤ a ≤ b ⟹ a × a ≤ a × b = n ⟹ 1 ≤ a ≤ $\sqrt{n}$ (với $a$ là $1$ ước dương của n).
$\Rightarrow$ chỉ cần duyệt trong đoạn [2, $\sqrt{n}$]**

:::
#### Ví dụ: Nếu chúng ta muốn kiểm tra xem số $17$ có phải là số nguyên tố hay không, thì chúng ta chỉ cần kiểm tra các ước số từ $2$ đến $sqrt(17) ≈ 4.12$. Trong trường hợp này, chúng ta chỉ cần kiểm tra ước số $2$ và $3$, không cần phải kiểm tra bất kỳ ước số nào lớn hơn căn bậc hai của $17$.

#### Code mẫu:

#include <bits/stdc++.h>
using namespace std;
int n;
bool check(int x) {
    if (x < 2) {
        return false;
    }
    for (int i=2;i<=int(sqrt(n));i++) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
   
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    if (check(n)) {
        cout << "TRUE";
    } else {
        cout << "FALSE";
    }
}

#### Độ phức tạp của thuật toán:
:::info
Độ phức tạp của thuật toán là $O(\sqrt{N})$.
:::

### **Kết luận**
:::success
**Thuật toán “trưởng thành” sẽ là lựa chọn tốt nhất nếu bạn muốn kiểm tra số nguyên tố thay vì ngây thơ sử dụng thuật toán “mầm non”.**
:::

## **Sàng nguyên tố Eratosthenes**
### Giải thuật
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 N có phải là nguyên tố hay không.


- **Bước 1:** Tạo 1 danh sách các số tự nhiên liên tiếp từ $2$ đến $(2, 3, 4,..., n)$.
- **Bước 2:** Giả sử tất cả các số trong danh sách đều là số nguyên tố. Trong đó, $p = 2$ là số nguyên tố đầu tiên.
- **Bước 3:** Tất cả các bội số của $p: 2p, 3p, 4p,...$ sẽ bị đánh dấu vì không phải là số nguyên tố.
- **Bước 4:** Tìm các số còn lại trong danh sách mà chưa bị đánh dấu và phải lớn hơn $p$ và nhỏ hơn hoặc bằng căn bậc 2 của n . Nếu không còn số nào, dừng tìm kiếm. Ngược lại, gán cho p giá trị bằng số nguyên tố tiếp theo và quay lại bước 3.
#### Khi giải thuật kết thúc, tất các số chưa bị đánh dấu trong danh sách là các số nguyên tố cần tìm.
### Code mẫu:

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

#### Độ phức tạp của thuật toán là: $O(N$ $log$ $log$ $N)$.
## Bài tập áp dụng
### Ví dụ
#### Đề bài: [SỐ NGUYÊN TỐ TRONG ĐOẠN](https://vinhdinhcoder.net/Problem/Details/4606)
#### Tóm tắt đề:
Cho $2$ số nguyên dương $a, b$. Có bao nhiêu số nguyên tố trong đoạn $[a, b]$.

**Dữ liệu nhập:**
:::success
- Dòng đầu tiên ghi số k là số các đoạn $[a, b]$

- Tiếp theo là $k$ dòng mỗi dòng ghi 2 số $a, b$.
:::

**Kết quả:**
:::success
- Gồm $k$ dòng, dòng thứ $i$ ghi một số là số các số nguyên tố trong đoạn $[a, b]$ thứ $i$ đã cho.
:::

**Ràng buộc:**

- $1 ≤ a ≤ b ≤ 1.000.000$

- $1 ≤ k ≤ 100$

##### Input
::: success
1
1 5
:::

##### Output
:::success
3
:::

**Giải thích**
- Trong đoạn $[1..5]$ có $3$ số nguyên tố: $2, 3, 5$.
:::spoiler
#### Lời giải
:::info
- Sử dụng sàng nguyên tố Eratosthenes để đánh dấu các số nguyên tố trong đoạn $[1..1e6]$ thay vì xây dựng hàm kiểm tra nguyên tố và sử dụng lại nhiều lần.
- Chạy vòng for từ $a$ đến $b$ để tìm ra và đếm số các số nguyên tố đã đánh dấu trong mảng nguyên tố đã sàng ở trên, sau đó xuất ra kết quả
:::
:::spoiler
#### Code tham khảo:

#include <bits/stdc++.h>
using namespace std;
int a,b,dem,k;
const int maxN = 1e6+5;
bool isPrime[maxN];

void sieve(int N) {
    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;
        }
    }
}

int main () {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> k;
	sieve(maxN);
	for (int i=1;i<=k;i++) {
		cin >> a >> b;
		dem = 0;
		for (int j=a;j<=b;j++) {
			if (isPrime[j] == true) {
				dem++;
			}
		}
		cout << dem << endl;
	}
	
	return 0;
}

:::
### Một số bài tập khác:
:::info
https://vinhdinhcoder.net/Problem/Details/4605

https://vinhdinhcoder.net/Problem/Details/4606

https://vinhdinhcoder.net/Problem/Details/4625
:::

## **Ước chung lớn nhất của hai số**
---

### 1. Định nghĩa
:::info
#### *[Ước chung lớn nhất](https://vi.wikipedia.org/wiki/%C6%AF%E1%BB%9Bc_s%E1%BB%91_chung_l%E1%BB%9Bn_nh%E1%BA%A5t) (GCD) hay (ƯCLN) của hai hay nhiều số nguyên là số nguyên dương lớn nhất là ước của tất cả các số đó.*
:::

### 2. Cách tìm GCD của hai số
### A. Thuật toán cơ bản
Ta có nhận xét sau:

$GCD(a,b) \le min(a, b) \le max(a, b) \le LCM(a,b)$

Vì thế ta có thể tìm $GCD$ của $a$ và $b$ bằng cách chạy từ $min(a, b)$ xuống $1$, giá trị đầu tiên là ước của cả $a$ và $b$ là $GCD$ cần tìm.

#### Thuật toán có độ phức tạp là $O(min(a, b))$

#### Code mẫu:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll a, b;
    cin >> a >> b;
    a = abs(a); b = abs(b); // đảm bảo các số đều là số dương
    if (a < b) swap(a, b); // mặc định a là giá trị lớn hơn, b là giá trị nhỏ hơn
    for (int i = b; i >= 1; --i){
        if (a % i == 0 && b % i == 0){
            cout << i;
            break;
        }
    }
    return 0;
}

### B. Thuật toán tối ưu Euclid
Tuy nhiên, để tối ưu hơn, người ta thường dùng thuật toán Euclid để tìm $GCD$ của hai số. Thuật toán hoạt động dựa trên 2 tính chất:
:::success
- $GCD(a, 0) = GCD(0, a) = a$ với $a ≠ 0$
- Nếu $m$ là số nguyên bất kỳ, thì $GCD(a + m*b, b) = GCD(a, b)$
:::

Tính chất $1$ là trường hợp cơ sở của thuật toán Euclid, tính chất $2$ giúp ta chia nhỏ bài toán lớn, phức tạp thành bài toán nhỏ, dễ giải hơn.

Theo đó, ta có thể lấy $a = a \% b$, hoán đổi hai số (vì số dư luôn bé hơn số chia) và lặp lại cho đến khi phần dư bằng $0$ thì ta sẽ tìm được $GCD$ của $a$ và $b$

:::info
#### Độ phức tạp của thuật toán là $O(\log min(a, b))$
:::

### Ví dụ
** **Yêu cầu:** Tính $GCD$ của $192$ và $78$.
Trước hết, ta thấy $192 ≠ 0$ và $78 ≠ 0$
Ta có $192 \% 78 = 36$
⇒ $GCD(192, 78) = GCD(78, 36)$
Ta lặp lại các bước cho đến khi phần dư bằng $0$:
$78 \% 36 = 6 ⇒ GCD(78, 36) = GCD(36, 6)$
$36 \% 6 = 0 ⇒ GCD(36, 6) = GCD(6, 0)$
Khi phần dư nhận được là $0$, **số còn lại ($\ne 0$) là kết quả cần tìm.**

#### Code mẫu:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll gcd(ll a, ll b)
{
    if (b == 0) return a;
    return gcd(b, a%b);
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll a, b;
    cin >> a >> b;
    cout << gcd(a, b);
    return 0;
}

### C. Hàm tìm GCD trong thư viện C++
Thư viện `<algorithm>` có sẵn hàm `__gcd(a,b)` để tìm của $a$ và $b$ nên đa phần mọi người dùng hàm có sẵn thay vì tự cài thuật toán.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll a, b;
    cin >> a >> b;
    cout << __gcd(a, b);
    return 0;
}

## Bội chung nhỏ nhất của hai số
### 1. Định nghĩa
:::info
#### [Bội chung nhỏ nhất](https://vi.wikipedia.org/wiki/B%E1%BB%99i_s%E1%BB%91_chung_nh%E1%BB%8F_nh%E1%BA%A5t#:~:text=Trong%20s%E1%BB%91%20h%E1%BB%8Dc%2C%20b%E1%BB%99i%20s%E1%BB%91,cho%20c%E1%BA%A3%20a%20v%C3%A0%20b) (LCM) hay (BCNN) của hai số nguyên $a, b$ là số nguyên dương nhỏ nhất chia hết cho cả $a$ và $b$.
:::

### 2. Thuật toán tìm LCM của hai số
### A. Thuật toán cơ bản
:::success
Dựa trên định nghĩa, ta có thể tìm $LCM$ bằng cách cộng $max(a, b)$ cho chính nó cho đến khi tìm được một tổng chia hết cho số còn lại.
:::
:::info
**Trong trường hợp tệ nhất, thuật toán có độ phức tạp là $O(min(a,b))$**
:::

#### Code mẫu:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll a, b;
    cin >> a >> b;
    a = abs(a); b = abs(b); // đảm bảo các số đều là số dương
    if (a < b) swap(a, b); // mặc định a là giá trị lớn hơn, b là giá trị nhỏ hơn
    for (int i = 1; i <= b; ++i){
        if (a*i % b == 0){
            cout << a*i;
            break;
        }
    }
    return 0;
}

### B. Thuật toán cải tiến
Ngoài ra, để tìm LCM của hai số, ta có thể áp dụng tính chất:
:::info
$GCD(a, b) * LCM(a, b) = a*b ⇔ LCM(a, b) = \frac{a*b}{GCD(a, b)}$
:::

:::success
**Khi đó, độ phức tạp của thuật toán là $O(log (min(a, b)))$**
:::

#### Code mẫu:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll a, b;
    cin >> a >> b;
    cout << a*b/__gcd(a, b);
    return 0;
}

Tuy nhiên công thúc này chỉ áp dụng được khi tìm LCM của 2 số và dễ bị tràn số trong một số trường hợp nên để tìm LCM của các số quá lớn hay nhiều số, ta cần phân tích các số ra thừa số nguyên tố rồi áp dụng công thức tính LCM đã học:
#### Code mẫu:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
vector<ll> a;
map<ll, int> mp;
void read(){
    cin >> n;
    ll m;
    for (int i = 0; i < n; ++i){
        cin >> m;
        a.push_back(abs(m)); // đảm bảo các số đều là số dương
    }
}
void factorise(ll num){
    int cnt;
	for (int i = 2; i*i <= num; ++i)
	{
	    cnt = 0;
		while (num % i == 0)
        {
            num /= i;
            ++cnt;
        }
        mp[i] = max(mp[i], cnt); // lưu số mũ có giá trị lớn nhất
		if (n == 1) break;
	}

	if (num != 1) mp[num] = max(mp[num], 1); 
}
ll lcm(){
    ll ans = 1;
    for (map<ll, int>::iterator it = mp.begin(); it != mp.end(); ++it) // duyệt qua các phần từ của map
        for (int j = 1; j <= it->second; ++j) 
        	ans *= it->first; // it->first lưu số nguyên tố.
        					 // it-> second lưu số mũ lớn nhất của số nguyên tố đó
    return ans;
}
int main()
{

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    read();
    for (int i = 0; i < n; ++i) factorise(a[i]);
    cout << lcm();
    return 0;
}

:::warning
#### **Lưu ý:** Các số âm cần được đổi dấu trước khi áp dụng các thuật toán tìm GCD và LCM.
:::

## Bài tập áp dụng:
### Ví dụ:
#### Đề bài: [Farmer And His Plot](https://www.codechef.com/problems/RECTSQ)
#### Tóm tắt đề:
:::warning
Cho $m, n$ là độ dài cạnh của một hình chữ nhật. Ta chia hình chữ nhật ra thành nhiều hình vuông có diện tích bằng nhau, tính số hình vuông nhỏ nhất chia được.
:::

:::spoiler
#### Nhận xét:
:::success
- Số hình vuông chia được càng nhỏ thì diện tích của hình vuông càng lớn.
- Diện tích các hình vuông bằng nhau $\Rightarrow$ cạnh của các hình vuông bằng nhau.
- Toàn bộ hình chữ nhật được chia ra thành các hình vuông $\Rightarrow$ cạnh hình vuông phải chia hết cho m, n.
$\Rightarrow$ Cạnh hình vuông là $GCD(m, n)$. Từ đó, ta có thể dễ dàng tìm ra số hình vuông nhỏ nhất chia được.
:::
:::spoiler
#### Code tham khảo:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll a, b, c;
    int t; 
    cin >> t;
    for (int i = 1; i <= t; ++i){
        cin >> a >> b;
        c = __gcd(a, b);
        c *= c; // diện tích của mỗi hình vuông
        cout << a*b/c << "\n"; // số hình vuông chia được
    }
    return 0;
}

:::
### Một số bài tập khác:
:::success
[GCD and LCM](https://www.codechef.com/problems/FLOW016)
[Apples and oranges](https://www.codechef.com/problems/APPLEORANGE)
[Appy and Contest](https://www.codechef.com/problems/HMAPPY2)
:::

## **Phân tích số nguyên**
### 1. Khái niệm
:::info
Trong lý thuyết số, phân tích số nguyên là việc phân tách một hợp số thành một tích của các số nguyên nhỏ hơn. Nếu các số nguyên đó giới hạn lại chỉ là số nguyên tố, quá trình được gọi là phân tích số nguyên thành thừa số nguyên tố.
:::

### 2. Thuật toán
#### A. Cách làm cơ bản

#### Ý tưởng
Ta sẽ chạy 1 vòng lặp gồm các số từ 2 đến $\sqrt{n}$ để thử hết tất cả những số có thể là thừa số nguyên tố và nếu số $n$ chia hết cho các số đó thì lặp lại quá trình đến khi kết thúc. Nếu $n$ không chia hết cho các số trong đoạn [2, $\sqrt{n}$] thì $n$ là thừa số nguyên tố cần tìm.
:::success

*Với cách tiếp cận này, độ phức tạp có được sẽ là: **$O(\sqrt{n})$***
:::
#### Code mẫu

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n;
    vector<int> v; // mảng động dùng để lưu trữ các thừa số nguyên tố của n

    for (int i=2; i*i<=n; ++i) {
        while (n % i == 0) {
            n/=i;
            v.push_back(i); // đẩy thừa số nguyên tố i vào trong vector
        }
    }

    if (n != 1) v.push_back(n); // nếu n > 1 nghĩa là n chính là thừa số nguyên tố còn lại cần tìm

    // in ra các thừa số nguyên tố đã tìm đc
    for (int t: v) cout << t << " ";

    return 0;
}

#### B. Dùng sàng nguyên tố Eratosthenes:
- **Nhận xét**
- **Ưu điểm** của cách này là phân tích thừa số nguyên tố chỉ trong $O(\log(n))$ thay vì $O(\sqrt{n})$ thế nên sàng sẽ giúp ta phân tích được nhiều số nhỏ ra thừa số nguyên với thời gian chạy nhanh hơn cách A.
- **Nhược điểm** là việc tiền xử lí sàng nguyên tố tốn độ phức tạp là $O(n*\log(n))$ như đã trình bày ở trên. Bên cạnh đó, để cài được sàng thì cần phải tạo được mảng có n phần tử, vì vậy những bài cho giới hạn $n$ quá lớn thì cách tiếp cận này không khả thi (ví dụ: $n > 3e8$).
- **Ý tưởng**:
- **Bước 1:** Dùng sàng nguyên tố để kiếm số nguyên tố nhỏ nhất là ước của từng số từ $2$ đến $n$ (vì tính chất của bài toán nên ta cần biến đổi sàng 1 chút so với thông thường). Sau đó duyệt lại 1 lần và gán thừa số nguyên tố nhỏ nhất của tất cả số nguyên tố là chính nó
- **Bước 2:** Hàm phân tích thừa số nguyên tố của các số n được truyền vào hàm
- **Bước 3:** In ra các kết quả cho từng truy vấn tương ứng

#### Code mẫu:

#include <bits/stdc++.h>
using namespace std;
//
const int N = 1e6;
vector <int> min_prime;
//
void eratosthenes_sieve()
{
    for (int i=2; i*i <= N; ++i)
    {
        if (min_prime[i] == 0) // nếu i là số nguyên tố thì chọn i để thử làm thừa số nguyên tố nhỏ nhất của các số j
            for (int j = i*i; j <= N; j+=i)
                if (min_prime[j] == 0) min_prime[j] = i; // nếu min_prime[j] != 0 nghĩa là min_prime[j] đã có 1 thừa số nguyên tố nhỏ hơn giá trị "i" đang xét
    }
    // kiểm tra các số nguyên tố và gán thừa số nguyên tố nhỏ nhất là chính nó
    for (int i=2; i <= N; ++i) if (min_prime[i]==0) min_prime[i] = i; // nếu min_prime[i] = 0 => i chính là số nguyên tố
}
//
vector <int> factorize(int n) // hàm để phân tích thừa số nguyên tố
{
    vector <int> v; // mảng lưu trữ các thừa số nguyên tố của n
    while (n > 1)
    {
        v.push_back(min_prime[n]); // đẩy thừa số nguyên tố nhỏ nhất của giá trị "n" hiện tại vào vector
        n /= min_prime[n]; // chia n cho thừa số nguyên tố đó
    }
    return v;
}
//
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);

    int query; cin >> query; // số lượng truy vấn

    min_prime.resize(N+1, 0);
    // gọi hàm sàng nguyên tố
    eratosthenes_sieve();
    //
    while (query--)
    {
        int n; cin >> n;
        //
        vector <int> ans = factorize(n);

        // in ra các thừa số nguyên tố của n
        for (int t: ans) cout << t << " ";
        cout << "\n";
    }

    return 0;
}

- Với cách tiếp cận này, độ phức tập có được là:
- $O(n*\log( \log(n)) + query*\log(n))$
- $n$: giá trị của các số được truy vấn
- $query$: số lượng truy vấn
- $n*\log(\log(n))$ cho việc tiền xử lí sàng nguyên tố, $query*\log(n)$ cho việc truy vấn và phân tích thừa số nguyên tố
- **Tính chất thú vị:**
:::warning
**Nếu $N = p_1^{q_1}*p_2^{q_2}...*p_k^{q_k}$ với $p_1, p_2,...,p_k$ là các số nguyên tố thì $N$ có $(q_1+1)*(q_2+1)...*(q_k+1)$ ước phân biệt**
:::
## Bài tập áp dụng:
### Ví dụ:
[CSES - Counting Divisors](https://cses.fi/problemset/task/1713/)

##### Đề bài
:::warning
- Cho $n$ số nguyên. Hãy đếm số ước của $n$ số nguyên $x$
:::
##### Input
:::success
- Dòng đầu tiên chứa $n$ là số lượng số nguyên
- Mỗi dòng trong $n$ dòng tiếp theo, nhập vào số nguyên $x$
:::

##### Output
:::success
- Với $n$ dòng, mỗi dòng in ra số lượng ước của số tương ứng
:::

##### Giới hạn
- $1 \le n \le 10^5$
- $1 \le x \le 10^6$
:::spoiler
#### Code tham khảo:

#include <bits/stdc++.h>
using namespace std;

signed main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);

    int n; cin >> n;
    while (n--)
    {
        int x; cin >> x;
        int ans = 1; // ans: số lượng ước của x
        // phân tích thừa số nguyên tố của x
        // áp dụng tính chất đã được nêu ra ở trên để đếm ước
        for (int i=2; i*i <= x; ++i)
        {
            if (x%i == 0)
            {
                int cnt = 0; // đếm số mũ của thừa số nguyên tố "i"
                while (x%i==0)
                {
                    x/=i;
                    cnt++;
                }
                ans *= (cnt+1);
            }
        }
        if (x > 1) ans *= 2;
        cout << ans << "\n";
    }
}

:::
#### Một số bài tập khác:
:::success
[k-Factorization (Codeforces)](https://codeforces.com/contest/797/problem/A)
[Strongly Composite (Codeforces)](https://codeforces.com/problemset/problem/1823/C)
[CHINUOC - ĐẾM SỐ CÓ 9 ƯỚC (Vinhdinhcoder)](https://vinhdinhcoder.net/Problem/Details/4640)
:::

## Tài liệu tham khảo:

:::warning
[Sàng Eratosthenes (Wikipedia)](https://vi.wikipedia.org/wiki/S%C3%A0ng_Eratosthenes)

[VNOI Wiki - Số nguyên tố (Prime Numbers)](https://vnoi.info/wiki/translate/he/Number-Theory-2.md#s%E1%BB%91-nguy%C3%AAn-t%E1%BB%91-prime-numbers)

[VNOI Wiki - phân tích thừa số nguyên tố bằng sàng Eratosthenes ](https://vnoi.info/wiki/translate/he/Number-Theory-2.md#ph%C3%A2n-t%C3%ADch-th%E1%BB%ABa-s%E1%BB%91-nguy%C3%AAn-t%E1%BB%91-v%E1%BB%9Bi-s%C3%A0ng-eratosthenes)

[CP Handbook (Antti Laaksonen)](https://cses.fi/book/book.pdf)

[Euclidean algorithms (Basic and Extended) (Geeksforgeeks)](https://www.geeksforgeeks.org/euclidean-algorithms-basic-and-extended/)

[Khan Academy - The Euclidean Algorithm](https://www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/the-euclidean-algorithm#:~:text=The%20Euclidean%20Algorithm%20for%20finding,%3D%20GCD(B%2CR))
:::
> [color=#9b46c9] Have a nice day. Bye!
###### tags: `tin trong toán` `2SG` `toán tin` `tin` `toán`