#include<bits/stdc++.h>
using namespace std;
bool cp(int n){
	if(n<2){
		return 0;
	}for(int i = 2;i< n;i++){
		if(n%i==0){
			return 0;
		}
	}
	return 1;
}
int main(){
	int l,r;

	
	int n;
	cin>> n;
    while(n--){
	
	int cnt = 0;
			cin>>l>>r;
		for(int i = l;i<=r ;i++){
			if(cp(i)==1){
				cnt++;
			}
		}
		
		cout<< cnt<< endl;
    }
	return 0; 
}

40 , TE , 这咋搞

3 comments

  • @ 2024-2-8 17:49:31
    void init2(int n){
    	flag[1]=1;
    	for(int i=2;i<=n;i++){
    		if(flag[i]==0){
    			p[tot]=i;
    			tot++;
    		}
    		for(int j=0;j<tot;j++){
    			if(i*p[j]>n){
    				break;
    			}
    			flag[i*p[j]]=1;
    			if(i%p[j]>n){
    				break;
    			}
    		} 
    	}
    	sum[1]=0;
    	for(int i=2;i<=n;i++){
    		if(flag[i]==0){
    			sum[i]=sum[i-1]+1;
    		}else{
    			sum[i]=sum[i-1];
    		}
    	}
    }
    void init(int n){
    	flag[1]=1;
    	for(int i=2;i*i<=n;i++){
    		if(flag[i]==0){
    			for(int j=i*i;j<=n;j++){
    				flag[j]=1;
    			}
    		}
    	}
    }
    bool isprime(int n){
    	if(n<=1){
    		return false;
    	}
    	for(int i=2;i*i<=n;i++){
    		if(n%i==0){
    			return false;
    		}
    	}
    	return true;
    }
    
    • @ 2024-2-8 9:26:41

      线性筛了解一下

      • @ 2024-2-7 22:58:07

        用前缀和优化一下

        • 1