#include<iostream> #include<algorithm> #include<cmath> #include<vector> using namespace std; vector<int> prime; const int MAX=1000001; bool h[MAX]={0}; void f(){ for(int i=2;i<MAX;i++){ if(h[i]==false) { prime.push_back(i); for(int j=i+i;j<MAX;j+=i){ h[j]=true; } } } } int main(){ long long a,b; f(); h[1]=true; while((scanf("%d %d",&a,&b))!=EOF){ vector<int>::iterator s1= lower_bound(prime.begin(),prime.end(), a); vector<int>::iterator s2= upper_bound(prime.begin(),prime.end(), b); printf("%d\n",distance(s1,s2)); } } |
Double click to view unformatted code.