Codeforces Round #226 (Div. 2) C Number Theory_html/css_WEB-ITnose

Title:

The CF machine is really powerful. It only ran for 600ms. It gave you a sequence of n numbers, and then asked m times. Each time you asked, find each number in the sequence. It is to count the multiples of several prime numbers in the interval [a, b], and then sum up the numbers. It is easy to understand after reading the hint below the question, and then I saw that the range of a and b is a bit large, 2*10^ 9. I don’t know how to deal with it, but later I discovered that the maximum number in the sequence is 10^7, so it doesn’t matter how big a and b are. There will be no prime numbers in the sequence that are larger than the maximum number in the sequence. A number is a multiple of it, and then the prime numbers within 10^7 are preprocessed, and the numbers in the sequence are counted. While preprocessing the prime numbers, there is a process of screening out the multiples of the prime numbers, which is here Determine whether the multiple of the prime number is in the sequence. If so, add the number of the number. Finally, find the prefix sum. Then the answer is sum[b] - sum[a - 1],

When screening prime numbers, the second for loop usually starts from 2*i, but there is no guarantee that there is no prime number in the sequence. For example, in the first case, there is 5 in the sequence, then 5 is a multiple of 5. If The second layer of loop will miss a part starting from 2*i. The habitual writing here made me stuck for a while, because the debugging there is not easy to do,

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;i<n;i++) {			int x;			scanf("%d",&x);			nnum[x]++;		}		return false;	}	return true;}void cal() {	get_prime();	int m;	scanf("%d",&m);	while(m--) {		int a,b;		scanf("%d %d",&a,&b);		a = a>10000000?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;}