Codeforces 385(#226 Div2 only) C. Bear and Prime Numbers

問題

n項からなる数列x[i]が与えられる。
素数pに対してf(p)は、xのうちpの倍数であるものの個数とする。


[l, r]が与えられるので、l以上r以下の素数p全てについてf(p)の和を求めよ、
というクエリがm個くるので答えよ。

制約条件

n≦10^6
m≦50000
x[i]≦10^7
l, r≦10^9

方針

x[i]を素因数分解しつつpで割れたらsum[p]に1を足す。
で、この累積和を計算すれば、l, rのクエリに対してsum[r] - sum[l - 1]を計算すれば、
クエリに対してはO(1)で答えを出すことができる。

ソースコード

const int MX = 10001000;
int n, m;
int p[MX], sum[MX];


int main(){
	for(int i = 2; i < MX; i++){
		if(p[i]) continue;
		p[i] = i;
		for(ll j = (ll)i * i; j < MX; j += i) p[j] = i;
	}
	
	cin >> n;
	
	rep(i, n){
		int a;
		cin >> a;
		
		while(a > 1){
			int b = p[a];
			sum[b]++;
			for(; a % b == 0; a /= b);
		}
	}
	rep(i, 10001000 - 1) sum[i + 1] += sum[i];
	
	cin >> m;
	
	while(m--){
		int l, r;
		cin >> l >> r;
		
		r = min(r, 10001000 - 1);
		l = min(l, r);
		cout << sum[r] - sum[l - 1] << endl;
	}
	return 0;
}