View Code of Problem 103

#include <iostream>
#include <string>
#include <cmath>		
#include <algorithm>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <queue>
using namespace std;
int main()
{
	int i, j, flag, k;
	int t, n, m;
	vector<int> nums(1000001, 0);//1000000个0
	for (i = 2; i <= sqrt(1000000); i++)
	{
		if (nums[i] != 1) {
			for (j = i * i; j <= 1000000; j += i)
			{
				nums[j] = 1;//4 6 8 10 12... 
							//9 27 52 18
			}
		}
	}
	vector<int> dp(1000001, 0);
	dp[2] = 1;
	//使用dp避免超时
	for (i = 3; i <= 1000000; i++)
	{
		if (nums[i] == 0)
			dp[i] = dp[i - 1] + 1;
		else
			dp[i] = dp[i - 1];
	}
	int a, b;
	while (cin >> a >> b) {
		int sum = 0;
		cout << dp[b] - dp[a - 1] << endl;
	}
	return 0;
}