View Code of Problem 103

#include<iostream>
#include<string>
#include <algorithm>
#include <iomanip>
#include <vector>
#include <cmath>
#include<cstring>
using namespace std;
int sh(int n)
{
	if (n == 0 || n == 1)
		return 0;
	if (n == 2 || n == 3)
	{
		return 1;
	}
	for (int i = 2;i < (int)sqrt(n) + 1;i++)
	{
		if(n%i == 0)
			return 0;
	}
	return 1;
}
int num[1000001] = { 0 };
int dp[1000001] = { 0 };
int main()
{
	memset(num, 0, sizeof(num));
	memset(dp, 0, sizeof(dp));
	num[0] = 1, num[1] = 1;
	int cnt = 0;
	for (int i = 2;i < 1000000;i++)
	{
		if (num[i] == 0)
		{
			cnt++;
			dp[i] = cnt;
			for (int j = i + i;j < 1000000;j = j + i)
				num[j] = 1;
		}
		else
			dp[i] = dp[i - 1];
	}
	int a, b;
	//int cnt = 0;
	while (cin >> a >> b)
	{
		int sum = dp[b] - dp[a];
		if (sh(a) == 1)
			sum++;
		cout << sum << endl;
	}
}