其中 $1 \leq L \leq 1000000, 1 \leq L \leq R \leq 1000000$。

我的想法是先预处理所有数（1~1000000）的结果，最后前缀和O(1)查询。

在算结果的时候我是先埃氏筛出1~1000000的所有素数，接着对每个数分解质因数算出答案。

这是我的代码，但是预处理超时了：

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

const int MAX = 1000000;

vector<int> primes;
int ans[MAX + 10];

void init_prime() {
	vector<bool> prime(MAX + 10, true);
	prime[2] = true;
	for (int i = 2; i <= MAX; i++) {
		if (prime[i]) {
			for (int j = i * 2; j <= MAX; j += i) {
				prime[j] = false;
			}
		}
	}
	for (int i = 2; i <= MAX; i++) {
		if (prime[i]) {
			primes.push_back(i);
		}
	}
}

void init_ans() {
	set<int> once, over_once;
	for (int i = 2; i <= MAX; i++) {
		int tmp = i;
		for (int j = 0; tmp > 1; j++) {
			while (tmp % primes[j] == 0) {
				if (once.find(primes[j]) == once.end()) {
					if (over_once.find(primes[j]) == over_once.end()) {
						once.insert(primes[j]);
					}
				} else {
					over_once.insert(primes[j]);
					once.erase(primes[j]);
				}
				tmp /= primes[j];
			}
		}
		ans[i] = ans[i - 1] + once.size();
	}
}

int main() {
	init_prime();
	init_ans();
	int t;
	cin >> t;
	while (t--) {
		int l, r;
		cin >> l >> r;
		cout << ans[r] - ans[l - 1] << endl;
	}
	return 0;
}

求助万能的谷民们，有没有什么好的优化方法和思路可以AC本题？