## Số nguyên tố

### 1. Khái niệm Số Nguyên Tố
Số nguyên tố là các số tự nhiên lớn hơn 1, chỉ chia hết cho 1 và chính nó. Ví dụ như 2, 3, 5, 7,...
#### Thuật toán Kiểm Tra Số Nguyên Tố

Để kiểm tra xem một số $n$ có phải là số nguyên tố không, ta có thể sử dụng các thuật toán sau đây. Một số được coi là nguyên tố nếu nó lớn hơn 1 và không chia hết cho bất kỳ số nào khác ngoài 1 và chính nó.

### 1. Thuật toán Kiểm Tra Cơ Bản
Phương pháp cơ bản kiểm tra số nguyên tố là duyệt qua tất cả các số từ 2 đến $( n - 1 )$ và kiểm tra xem $( n )$ có chia hết cho bất kỳ số nào không. Nếu có, $( n )$ không phải là số nguyên tố.
1. Nếu $( n \leq 1 )$, trả về `False` (không phải số nguyên tố).
2. Duyệt từ $( i = 2 )$ đến $( n - 1 )$:
- Nếu $( n )$ chia hết cho $( i )$ (tức là $( n \% i = 0 ))$, trả về `False`.
3. Nếu không chia hết cho bất kỳ $( i )$ nào, trả về `True` (là số nguyên tố).

**Độ phức tạp**: $( O(n) )$.

### 2. Thuật toán Tối Ưu Hóa với Căn Bậc Hai
Một cách tối ưu hơn là chỉ cần kiểm tra đến $( \sqrt{n} )$ thay vì $( n - 1 )$, bởi nếu $( n = a \times b )$ và $( n )$ không phải là số nguyên tố thì ít nhất một trong hai số $( a )$ hoặc $( b )$ sẽ nhỏ hơn hoặc bằng $( \sqrt{n} )$.
1. Nếu $( n \leq 1 )$, trả về `False`.
4. Duyệt $( i )$ từ 2 đến $(\sqrt{n} )$:
- Nếu $( n \mod i = 0 )$, trả về `False`.
5. Nếu không chia hết cho bất kỳ $( i )$ nào, trả về `True`.

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

### 2. Thuật toán Sàng Nguyên Tố
Thuật toán sàng nguyên tố Eratosthenes là một cách hiệu quả để tìm tất cả các số nguyên tố nhỏ hơn hoặc bằng một số $( n )$ cho trước. Đây là một trong những thuật toán cổ xưa và hiệu quả nhất để xác định số nguyên tố.

**Ý tưởng của thuật toán:**
1. Tạo một mảng đánh dấu tất cả các số từ 2 đến $( n )$ là nguyên tố.
2. Bắt đầu từ số 2 (số nguyên tố nhỏ nhất), loại bỏ tất cả các bội của nó (tức là đánh dấu các số này không phải nguyên tố).
3. Chuyển sang số tiếp theo chưa bị loại bỏ và lặp lại cho đến khi xử lý hết các số có $( \sqrt{n} )$.
4. Cuối cùng, các số chưa bị loại bỏ là các số nguyên tố.

**Các bước chi tiết của thuật toán:**
- Bước 1: Tạo mảng đánh dấu `isPrime[]` với tất cả các giá trị là `True`.
- Bước 2: Bắt đầu từ $( i = 2 )$, nếu `isPrime[i]` là `True`, đánh dấu tất cả các bội của $( i )$ từ $( i^2 )$ đến $( n )$ là `False`.
- Bước 3: Tăng $( i )$ lên và lặp lại cho đến khi $( i^2 > n )$.
- Bước 4: Các chỉ số còn lại có giá trị `True` trong mảng là các số nguyên tố.

#### Độ phức tạp của thuật toán
Thuật toán này có độ phức tạp $( O(n \log (\log n) )$, là một trong những thuật toán nhanh nhất để tìm số nguyên tố trong một phạm vi lớn.

void sieve(int n) {
    vector<bool> isPrime(n + 1, true);
    isPrime[0] = isPrime[1] = false; // 0 và 1 không phải là số nguyên tố

    for (int p = 2; p * p <= n; ++p) {
        if (isPrime[p]) {
            for (int i = p * p; i <= n; i += p) {
                isPrime[i] = false; // Đánh dấu các bội số của p là không phải số nguyên tố
            }
        }
    }
}

#### Ứng dụng của Thuật toán Sàng Nguyên Tố
- Tìm tập hợp các số nguyên tố trong phạm vi lớn
- Ứng dụng trong mật mã học, phân tích thừa số, và các bài toán yêu cầu tính nhanh

## Ước chung lớn nhất

### Định nghĩa
Ước chung lớn nhất (GCD) của hai số nguyên $( a )$ và $( b )$ là số nguyên lớn nhất mà cả hai số này đều chia hết. GCD thường được sử dụng trong nhiều ứng dụng toán học, đặc biệt là trong lý thuyết số.

### Phương pháp Euclid
Thuật toán Euclid là một trong những phương pháp hiệu quả nhất để tìm GCD. Cơ sở của thuật toán này là định lý rằng GCD của hai số $( a )$ và $( b )$ cũng bằng GCD của $( b )$ và $( a \% b )$.

#### Đoạn mã C++
Dưới đây là đoạn mã C++ triển khai thuật toán cải tiến:

int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}
// hoặc cx có thể dùng hàm có sẵn trong c++ là __gcd(a,b)

## Bội chung nhỏ nhất
### Định nghĩa

Trong số học, **bội chung nhỏ nhất** của hai số $a$ và $b$ là số nguyên dương nhỏ nhất chia hết được cho cả hai $a$ và $b$. Nếu $a$ hoặc $b$ là 0, thì không tồn tại số nguyên dương nào chia hết cho $a$ và $b$, khi đó quy ước rằng $LCM(a, b) = 0$.

Với định nghĩa trên, ta tổng quát hóa lên cho nhiều số nguyên dương. Bội chung nhỏ nhất của $a_1, a_2, a_3, \dots, a_{n-1}, a_n$ là số nguyên dương nhỏ nhất mà là bội số của $a_1, a_2, a_3, \dots, a_{n-1}, a_n$.

### Ký hiệu

Bội chung nhỏ nhất của cặp số $a$ và $b$ được ký hiệu là $[a, b], BCNN(a,b)$ hoặc $LCM(a, b)$.

Ký hiệu tương tự cho bội chung nhỏ nhất của $a_1, a_2, a_3, \dots, a_{n-1}, a_n$.

### Cách tính BCNN

Có tổng cộng 2 cách chính để có thể tính được **bội chung nhỏ nhất** của hai số $a$ và $b$: Tính qua **ước số chung lớn nhất** và phân tích thừa số nguyên tố.

#### Tính qua ước chung lớn nhất

Công thức thể hiện mối quan hệ giữa $UCLN$ và $BCNN$ dưới đây sẽ tính được $BCNN$ của hai số bất kì $a$ và $b$:

                                              $BCNN(a, b) \ = \ \frac{|a \times b|}{UCLN(a, b)}$

#include <bits/stdio.h>
#include <cmath>
using namespace std;

// Hàm tính BCNN dựa trên UCLN
int BCNN(int a, int b) {
    return abs(a * b) / __gcd(a, b);
}

#### Tính BCNN bằng cách phân tích thừa số nguyên tố

Mở đầu, định lý cơ bản của số học nói rằng mọi số nguyên dương > $1$ đều có thể được biểu diễn một cách duy nhất dạng tích các số nguyên tố. Vì vậy, các hợp số có thể coi như là tích của các số nguyên tố cấu thành. Ví dụ:

                                             $100 = 2^2 \times 5^2 = 2 \times 2 \times 5 \times 5$

Dựa vào kiến thức này, chúng ta có thể tính được giá trị $BCNN$ cần tìm của một tập hợp các hợp số.

**Ví dụ**: $BCNN(8, 9, 30) = \ ?$

- Đầu tiên, ta sẽ phân tích các số trong tập hợp trên ra thành tích của các số nguyên tố:
                                                         $8 = 2^3$
                                                         $9 = 3^2$
                                                         $30 = 2 \times 3 \times 5$

Với mỗi số nguyên tố thì ta sẽ nâng lũy thừa bậc cao nhất và từ đó ta sẽ được giá trị của $BCNN$ cần tìm. Các số nguyên tố $2 , 3, 5$ có bậc cao nhất lần lượt là $2^3, 3^2, 5^1$. Do đó,
                                            $BCNN(8, 9, 30) = 2^3 \times 3^2 \times 5^1 = 360$

#include <bits/stdio.h>
#include <map>
#include <cmath>
using namespace std;

// Hàm phân tích một số n thành các thừa số nguyên tố
map<int, int> primeFactorization(int n) {
    map<int, int> factors;
    
    // Phân tích các thừa số 2
    while (n % 2 == 0) {
        factors[2]++;
        n /= 2;
    }
    
    // Phân tích các số nguyên tố lẻ
    for (int i = 3; i <= sqrt(n); i += 2) {
        while (n % i == 0) {
            factors[i]++;
            n /= i;
        }
    }
    
    // Nếu n là một số nguyên tố lớn hơn 2
    if (n > 2) {
        factors[n]++;
    }
    
    return factors;
}

// Hàm tính BCNN dựa trên phân tích thừa số nguyên tố
int LCM(int a, int b) {
    map<int, int> factorsA = primeFactorization(a);
    map<int, int> factorsB = primeFactorization(b);
    map<int, int> lcmFactors;
    
    // Hợp các thừa số với số mũ lớn nhất từ cả hai
    for (auto &factor : factorsA) {
        lcmFactors[factor.first] = max(factor.second, factorsB[factor.first]);
    }
    
    for (auto &factor : factorsB) {
        lcmFactors[factor.first] = max(factor.second, lcmFactors[factor.first]);
    }
    
    // Tính tích các thừa số để ra BCNN
    int lcm = 1;
    for (auto &factor : lcmFactors) {
        lcm *= pow(factor.first, factor.second);
    }
    
    return lcm;
}

int main() {
    int a, b;
    cout << "Nhap gia tri a: ";
    cin >> a;
    cout << "Nhap gia tri b: ";
    cin >> b;

    int result = LCM(a, b);
    cout << "BCNN(" << a << ", " << b << ") = " << result << endl;
    return 0;
}