第一眼看这道题目的时候觉得可能会很难也看不太懂，但是看了给出的Hint之后思路就十分清晰了
Consider the first sample. Overall, the first sample has 3 queries. The first query l = 2, r = 11 comes. You need to count f(2) + f(3) + f(5) + f(7) + f(11) = 2 + 1 + 4 + 2 + 0 = 9.
The second query comes l = 3, r = 12. You need to count f(3) + f(5) + f(7) + f(11) = 1 + 4 + 2 + 0 = 7.
The third query comes l = 4, r = 4. As this interval has no prime numbers, then the sum equals 0.
xn的范围在(2 ≤ xi ≤ 107)，而 l, r 的范围在 (2 ≤ li ≤ ri ≤ 2·109) ，易得在计算的时候是不会考虑107 以后了
首先写一个素数快速打表，同时也统计一下在 l, r 范围内每个数满足题目条件的总数 (虽然觉得这样的打表方法的确很慢)
然后注意了，因为查询的次数很多，多达5*104次 ，所以在统计的时候可以算出累计和以节省时间
Source Code:
//#pragma comment(linker, "/STACK:16777216") //for c++ Compiler
#include <stdio.h>
#include <iostream>
#include <fstream>
#include <cstring>
#include <cmath>
#include <stack>
#include <string>
#include <map>
#include <set>
#include <list>
#include <queue>
#include <vector>
#include <algorithm>
#define Max(a,b) (((a) > (b)) ? (a) : (b))
#define Min(a,b) (((a) < (b)) ? (a) : (b))
#define Abs(x) (((x) > 0) ? (x) : (-(x)))
#define MOD 1000000007
#define pi acos(-1.0) using namespace std; typedef long long ll ;
typedef unsigned long long ull ;
typedef unsigned int uint ;
typedef unsigned char uchar ; template<class T> inline void checkmin(T &a,T b){if(a>b) a=b;}
template<class T> inline void checkmax(T &a,T b){if(a<b) a=b;} const double eps = 1e- ;
const int N = ;
const int M = * ;
const ll P = 10000000097ll ;
const int MAXN = ; int cnt[MAXN],a[MAXN];
bool check[MAXN]; void init_prime(){
for(int i = ; i < MAXN; ++i){ //素数打表
if(!check[i]){
for(int j = i; j < MAXN; j += i){
check[j] = true;
cnt[i] += a[j];
}
}
}
} int main(){
std::ios::sync_with_stdio(false);
int i, j, t, k, u, v, numCase = ;
int n, q, x, y;
cin >> n;
for(i = ; i <= n; ++i){
cin >> x;
++a[x];
}
init_prime();
for(i = ; i < MAXN; ++i){
cnt[i] += cnt[i - ]; //作累计和以节省查询时间
}
cin >> t;
while(t--){
cin >> x >> y;
checkmin(x, );
checkmin(y, );
cout << cnt[y] - cnt[x - ] << endl;
}
return ;
}