View Code of Problem 103

#include<bits/stdc++.h>
using namespace std;
 
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;
	}
}