Toán & số học

4. Sàng Eratosthenes

Ý tưởng: viết mọi số từ 2 đến N. Lấy số nguyên tố nhỏ nhất chưa bị gạch (2), gạch bỏ mọi bội của nó. Số chưa bị gạch tiếp theo (3) lại là nguyên tố — gạch bội của 3. Cứ thế. Các số còn sót lại chính là số nguyên tố.

Sàng Eratosthenes từ 2 đến 31. Lần lượt gạch bội của 2, rồi bội của 3, rồi bội của 5. Mỗi số khi được chọn làm "sàng" đều là số nguyên tố; các số bị gạch là hợp số. Những số còn lại (tô xanh) là số nguyên tố.
sang.cpp
const int N = 1000000;
bool hopSo[N + 1] = {false};      // hopSo[x] = true neu x la hop so

for (int i = 2; (long long)i * i <= N; i++) {
    if (!hopSo[i]) {              // i con nguyen to
        for (int j = i * i; j <= N; j += i)
            hopSo[j] = true;     // gach moi boi cua i
    }
}
// x la nguyen to khi x >= 2 va !hopSo[x]
Vì sao bắt đầu gạch từ i*i?

Mọi bội nhỏ hơn i2i^2 (như 2i,3i,…2i, 3i, \ldots) đều đã bị gạch bởi các số nguyên tố nhỏ hơn i. Bắt đầu từ i⋅ii \cdot i tránh làm lại việc thừa.

Sàng tính xong toàn bộ số nguyên tố tới một triệu gần như tức thì — nhanh hơn rất nhiều so với kiểm tra từng số.

5. Phân tích thừa số nguyên tố

Mọi số nguyên đều viết được thành tích các số nguyên tố, ví dụ 360=23⋅32⋅5360 = 2^3 \cdot 3^2 \cdot 5. Ta lần lượt chia hết cho 2, rồi 3, rồi 5, ...

phan-tich.cpp
int n;
cin >> n;
for (int p = 2; (long long)p * p <= n; p++) {
    while (n % p == 0) {        // chia het cho p bao nhieu lan
        cout << p << " ";
        n /= p;
    }
}
if (n > 1) cout << n;            // phan con lai la 1 so nguyen to lon