UVa 11408 - Count DePrimes

// UVa 11408 - Count DePrimes

#include <iostream>
#include <string.h>
using namespace std;

#define integer unsigned long long

integer T[5000001];
integer sum[5000001];
bool is_prime[5000001];

int main() {
	memset(is_prime, true, sizeof(is_prime));
	memset(sum, 0, sizeof(sum));
	// sieve
	for (integer i = 2; i <= 5000000; i++)
		if (is_prime[i]) {
			for (integer j = (i << 1); j <= 5000000; j += i) {
				is_prime[j] = false;
				sum[j] += i;
			}
		}
	// DePrimes
	T[0] = 0;
	T[1] = 0;
	for (integer i = 2; i <= 5000000; i++)
		if (is_prime[i] || is_prime[sum[i]])
			T[i] = T[i - 1] + 1;
		else
			T[i] = T[i - 1];
	// input/output
	integer a, b;
	while ((cin >> a) && a) {
		cin >> b;
		cout << T[b] - T[a - 1] << endl;
	}

	return 0;
}