# Số nguyên tố, Sàng Eratosthenes
## Số nguyên tố
### Thuật toán "ngây thơ"
Ta sẽ duyệt hết tất cả các số từ 1 đến $N$ và đếm số ước của $N$. Nếu số ước của $N$ là 2 thì $N$ là số nguyên tố, nếu không thì $N$ không là số nguyên tố.

bool isPrime(int n) {
    for (int i = 2; i < n; i++)
        if (n % i == 0) {
            // n chia hết cho số khác 1 và chính nó.
            return false;
        }
    return n > 1;
}

Độ phức tạp: $O(N)$.
### Một thuật toán tốt hơn
Ta sẽ duyệt các số từ 1 đến $\sqrt{N}$.

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

Độ phức tạp: $O(\sqrt{N})$.
## Sàng Eratosthenes
Sàng nguyên tố dùng để tìm các số nguyên tố nhỏ hơn hoặc bằng $N$.

Nguyên lí hoạt động của sàng là vào mỗi lần duyệt, ta chọn một số nguyên tố và loại ra khỏi sàng tất cả các bội của số nguyên tố đó mà lớn hơn số đó. Sau khi duyệt xong, các số còn lại trong sàng đều là số nguyên tố.

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) {
             //Đánh dấu tất cả các bội của i là hợp số
             for(int j = i * i; j <= N; j += i)
                 isPrime[j] = false;
        }
    }
}

Độ phức tạp: $O(N log N)$.

## Phân tích thừa số nguyên tố với sàng Eratosthenes

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

Độ phức tạp: $O(\sqrt{N})$.