View Code of Problem 103

#include<iostream>
#include<vector>
using namespace std;
int main() {
	int a,b;
	vector<bool> v(1000001,1);
	vector<int> sum(1000001,0);
	v[1]=0;
	//埃拉托色尼筛选算法 
	for(int i=2; i<=1000000; i++) {
		if(v[i]) {
			for(int j=i*2; j<=1000000; j+=i) v[j]=0;
		}
	}
	//不用动归会超时! 
	//1-i范围内素数的个数
	for(int i=2; i<=1000000; i++) {
		if(v[i]) sum[i]=sum[i-1]+1;
		else sum[i]=sum[i-1];
 	} 
	while(cin>>a>>b) {
		//[a,b] 
		cout<<sum[b]-sum[a-1]<<endl;
	}
}