问题 C: 几乎是素数

题目描述

原题面

Almost prime numbers are the non-prime numbers which are divisible by only a single prime number.

In this problem your job is to write a program which finds out the number of almost prime numbers within a certain range.

Info

Wikipedia 关于“几乎是素数数”的介绍：Almost prime - Wikipedia

输入要求

First line of the input file contains an integer \(N (N \le 600)\) which indicates how many sets of inputs are there. Each of the next N lines make a single set of input. Each set contains two integer numbers low and high \((0 < low \ge high < 1012)\).

输出要求

For each line of input except the first line you should produce one line of output. This line contains a single integer, which indicates how many almost prime numbers are within the range (inclusive) low . . . high.

样例

3
4
1

解法

解法和时间复杂度： (1)

此处时间复杂度为该解法的算法部分的时间复杂度，不是严谨的整题的时间复杂度

埃式筛 + 二分查找 \(O(n\log n)\)

埃式筛 + 二分查找

Warning

注意二分查找中 lower_bound() 和 upper_bound()。

#include <bits/stdc++.h>
#define int long long int
using namespace std;
const int MAXn = 1e6 + 9, MAX = 1e12 + 9;
vector<int> prime;
bool notp[MAXn + 9];

signed main() {
    for(int i = 2; i <= MAXn; i ++) {
        if(!notp[i]) {
            for(int j = i * i; j <= MAXn; j += i) notp[j] = true;
            for(int j = i * i; j <= MAX; j *= i) prime.push_back(j);
        }
    }
    sort(prime.begin(), prime.end());
    int l, r;
    scanf("%lld%lld", &l, &r);
    auto pl = lower_bound(prime.begin(), prime.end(), l);
    auto pr = upper_bound(prime.begin(), prime.end(), r);
    printf("%lld\n", pr - pl);
    return 0;
}