CodeforcesRound#226(Div.2)C数论_html/css_WEB-ITnose

CF机子真心强大啊，这样才跑了600ms，给了你n个数的序列，然后m次询问，每次询问求出序列中每个数是 区间[a,b]内的 几个素数的倍数统计一下，然后对于个数求和，看了题目下面的hint很易懂，然后看到a,b的范围有些大哈，2*10^9，不知道怎么处理，但是后来发现，序列中的数 最大为10^7，所以就算a,b,再大也无所谓的，大于序列中的最大数的部分的素数，序列中不会有任何数 是它倍数的，然后就是对10^7以内的 素数进行预处理，同时把序列中的数统计一下个数，在预处理素数的同时 会有一个筛选祛除 该素数倍数的过程，就在这里判断一下该素数的倍数是否在序列中，若在就加上该数的个数，最后求一下前缀和，然后 答案就是 sum[b] - sum[a - 1]了，

在筛选素数的时候 第二个for循环一般都是 从2*i,开始的，但是 不保证序列中没有素数哈，比如说第一个案例，序列中有5，那么5是5的倍数，如果第二层循环从2*i开始就会漏掉一部分，这里习惯性的写法，让我卡了一会，因为 那里调试不太好弄，

int n;int nnum[10000000 + 55];bool isprime[10000000 + 55];int prime[10000000 + 55];int k;void get_prime() {	memset(isprime,false,sizeof(isprime));	for(int i=2;i<10000005 ;i++) {		if(!isprime[i])			for(int j=i /*2 * i*/;j<10000005;j+=i) {				isprime[j]=true;				if(nnum[j])prime[i] += nnum[j];			}	}	//for(int i=2;i<1000005;i++)	//	if(!isprime[i])	//		prime[k++]=i;	for(int i=1;i<10000005;i++)		prime[i] += prime[i - 1];}void init() {	memset(prime,0,sizeof(prime));	memset(nnum,0,sizeof(nnum));}bool input() {	while(cin>>n) {		for(int i=0;i10000000?10000000:a;		b = b>10000000?10000000:b;		printf("%d\n",prime[b] - prime[a - 1]);	}}void output() {}int main() {	while(true) {		init();		if(input())return 0;		cal();		output();	}	return 0;}