Hướng giải của Số nguyên tố (Olympic 30/4 K10 - 2019)

Nhớ rằng hướng dẫn giải này chỉ nên sử dụng khi bế tắc, và tuyệt đối không nên sao chép mã nguồn kèm theo. Hãy tôn trọng tác giả bài tập và người viết hướng dẫn giải.
Nộp mã nguồn lời giải chính thức trước khi giải bài tập đó có thể khiến bạn bị ban.

🤖 Ý tưởng giải thuật: Đếm số nguyên tố trong đoạn [L, R] nhanh

🌐 Bài toán:

Cho T truy vấn, mỗi truy vấn là một đoạn [L,R] (R≤109), cần đếm bao nhiêu số nguyên tố trong đoạn đó.

🔍 Nhận xét:
  • R có thể lớn đến 109, không thể sàng nguyên tố từ 1 đến R.
  • Tuy nhiên, tổng độ dài các đoạn truy vấn ≤ 10^6, ta có thể dùng Segmented Sieve cho từng đoạn.

🚀 Thuật toán:

Bước 1: Tiền xử sàng nguyên tố gốc (base primes)
  • Sàng nguyên tố từ 2 đến 109≈31623
  • Lưu các nguyên tố này vào một mảng base_primes
Sao chép
for (int i = 3; i <= 35000; i += 2)
    if (is_prime[i])
        base_primes.push_back(i);
Bước 2: Đối với mỗi truy vấn [L,R], dùng segmented sieve:
  1. Tạo mảng bool is_segment_prime[r - l + 1], khởi tạo toàn true
  2. Duyệt từng p trong base_primes, đánh dấu các bội số của p trong [L,R]
  3. Đếm bao nhiêu chỉ số i sao cho L + i là nguyên tố (mark[i] = true)
Lưu ý:
  • Xử lý riêng số 2
  • Đảm bảo đánh dấu từ max(p×p,⌈L/p⌉×p)
  • Bỏ qua số chẳn, chỉ xét số lẻ

📊 Độ phức tạp:

  • Sàng base: O(R)
  • Mỗi truy vấn: O((R−L+1)⋅log⁡log⁡R)
  • Tổng truy vấn đảm bảo chạy nhanh vì ∑(R−L+1)≤106
Sao chép
#include <bits/stdc++.h>
using namespace std;

const int MAX_PRIME = 35000;
vector<int> base_primes;          // các số nguyên tố nhỏ dùng cho segment sieve
vector<bool> is_prime(MAX_PRIME + 1, true);

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Tiền xử lý sàng các số lẻ đến 35000 (bỏ số chẵn trừ 2)
    for (int i = 3; i <= MAX_PRIME; i += 2) {
        if (is_prime[i]) {
            base_primes.push_back(i);
            int step = i * 2;
            if (i <= 188) { // i * i <= 35000
                for (int j = i * 3; j <= MAX_PRIME; j += step) {
                    is_prime[j] = false;
                }
            }
        }
    }

    int T;
    cin >> T;
    while (T--) {
        int l, r;
        cin >> l >> r;

        int count = 0;
        vector<bool> is_segment_prime(r - l + 1, true);

        // Đặc biệt xử lý số 2
        if (l <= 2 && r >= 2) {
            count++;
        }

        int start = max(l, 3);
        for (int p : base_primes) {
            if (1LL * p * p > r) break;
            int step = p * 2;

            // Tìm vị trí bắt đầu đánh dấu
            int j = max(p * 3, l + (l % p != 0) * p - (l % p));
            if ((j & 1) == 0) j += p; // đảm bảo j là số lẻ

            // Đánh dấu các số không phải nguyên tố
            for (; j <= r; j += step) {
                is_segment_prime[j - l] = false;
            }
        }

        // Đếm các số lẻ nguyên tố trong đoạn [l, r]
        for (int i = max(start, (start | 1)); i <= r; i += 2) {
            if (is_segment_prime[i - l]) {
                count++;
            }
        }

        cout << count << '\n';
    }

    return 0;
}

Nhận xét

Không có ý kiến tại thời điểm này.