10539 Almost Prime Numbers

題目敘述

題目說明：Almost Prime Numbers（近似質數）

一個數若是某個質數的整數次方（且次方 ≥ 2），這種數我們稱為「近似質數（Almost Prime）」，也就是：

p^k，其中 p 是質數，k ≥ 2 且 p^k ≤ 10¹²
給定多組查詢範圍，請找出在每個範圍內有多少個「近似質數」。

輸入說明

第一行：一個整數 N（1 ≤ N ≤ 600），代表查詢次數
接下來 N 行：每行兩個整數 low 和 high（0 < low ≤ high < 10¹²）

輸出說明

對每一組查詢，輸出該範圍內的近似質數個數（包含 low 與 high）

解題思路

這題要求計算區間 [low,high] 中有多少個「幾乎質數（almost prime）」，即形如的數，其中： 由於查詢次數最多為 600 次，而範圍最大到，我們無法暴力每次都重新計算，因此採取 預處理 + 二分搜尋 的策略，大致分為以下三個步驟：

步驟一：建立質數表（pbuide())
利用線性篩法（Linear Sieve）來建立以下的質數表儲存所有質數在 ps 向量中

步驟二：預先生成所有幾乎質數（generate_almost_primes())
對每個質數p²開始乘上自己，不斷生成直到大於10¹²停止，所有合法的p²加入 almost_primes 向量中，排序這個列表，方便之後查詢用二分搜尋

步驟三：對每組區間使用二分搜尋查詢（count_almost_primes())
使用 lower_bound 和 upper_bound 快速找出範圍 [low,high] 中的幾乎質數個數

程式碼

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

const long long PEND = 1e6;      // 質數範圍 (10^6)
const long long UPPER_LIMIT = 1e12; // 幾乎質數最大範圍 (10^12)

bitset<PEND> isp;
vector<long long> ps;            // 質數列表
vector<long long> almost_primes; // 幾乎質數列表

// 線性篩法建質數表
void pbuide() {
    isp.set();
    isp[0] = isp[1] = 0;
    for (long long i = 2; i < PEND; i++) {
        if (isp[i]) ps.push_back(i);
        for (auto &p : ps) {
            if (i * p >= PEND) break;
            isp[i * p] = 0;
            if (i % p == 0) break;
        }
    }
}

// 生成所有幾乎質數 (p^k)，確保不超過 10^12
void generate_almost_primes() {
    for (long long p : ps) {
        long long x = p * p; // 幾乎質數最小為 p^2
        while (x <= UPPER_LIMIT) {
            almost_primes.push_back(x);
            x *= p;
        }
    }
    sort(almost_primes.begin(), almost_primes.end()); // 排序以利二分搜尋
}

// 計算 [low, high] 內的幾乎質數數量
int count_almost_primes(long long low, long long high) {
    return upper_bound(almost_primes.begin(), almost_primes.end(), high) -
           lower_bound(almost_primes.begin(), almost_primes.end(), low);
}

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

    pbuide();                  // 建立質數表
    generate_almost_primes();  // 生成幾乎質數

    int n;
    cin >> n;
    while (n--) {
        long long a, b;
        cin >> a >> b;
        cout << count_almost_primes(a, b) << "\n";
    }

    return 0;
}