View Code of Problem 103

#include <cstdio>
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
using namespace std;

//bool isprime(int n){
//	if(n==1)
//		return false;
//	else{
//		for(int i=2;i<=sqrt(n*1.0);i++){
//			if(n%i==0)
//				return false;
//		}
//		return true;
//	}
//}
bool prime[1000001]={0};//设置素数表都为素数！！ 
int dp[1000001]={0};
//void printprime(){
//	int count=0;
//	for(int i=1;i<=1000000;i++){
//		if(isprime(i)){
//			prime[i]=i;
//			count++;
//		}
//		dp[i]=count;
//	}
//}
void printprime(){
	int count=0;
	for(int i=2;i<1000001;i++){
		if(prime[i]==false){
			for(int j=i+i;j<1000001;j+=i){
				prime[j]=true;
			}
			count++;
		}
		dp[i]=count;
	}
	prime[1]=true; 
}

int main(){
	int a,b;
	printprime();
	while(cin>>a>>b){
		int a1,b1; 
		int res;
		if(prime[b]&&!prime[a]){
			
			res=dp[b]-(dp[a]-1);
		}
		else if(prime[b]&&prime[a]||(!prime[b]&&prime[a]))
			res=dp[b]-dp[a];
		else if(!prime[b]&&!prime[a]) 
			res=dp[b]-dp[a]+1;
		cout<<res<<endl;
	}
	return 0;
}