View Code of Problem 103

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<climits>
#include<cmath>
#include<unordered_map>
#include<set>

using namespace std;

//bool judge(int num) {
//
//	if (num == 1)
//		return false;
//
//	for (int i = 2; i <= sqrt(num); i++) {
//
//		if (num % i == 0)
//			return false;
//	}
//
//	return true;
//}

int main()
{
	int a, b;

	vector<bool> primes(1000002, true);

	for (int i = 2; i <= 1000001; i++) {	//埃拉托色尼筛选算法

		if (primes[i]) {

			for (int j = i + i; j <= 1000001; j += i)
				primes[j] = false;
		}
	}

	vector<int> dp(1000002, 0);
	for (int i = 2; i <= 1000001; i++) {

		if (primes[i])
			dp[i] = dp[i - 1] + 1;
		else
			dp[i] = dp[i - 1];
	}


	while (cin >> a >> b) {

		cout << dp[b] - dp[a - 1] << endl;
	}
}