2141.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 2141 on 2006-03-06 at 20:43:18 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

typedef long long int64;
const int MAX = 45000;
const int LIMIT = 2000000000;

bool prime[MAX];
int p[5120], pn = 0;

bool isPrime(int);

int main()
{
	int i, j, t, T;
	int exp[512], en = 0;

	memset(prime, true, sizeof(prime));
	for(i = 2; i < MAX; i++) {
		if(!prime[i]) continue;
		p[pn++] = i;
		for(j = 2; i*j < MAX; j++) prime[i*j] = false;
	}
	int x = upper_bound(p, p+pn, 1300) - p;
	for(i = 0; i < x; i++)
		for(j = 1; true; j++) {
			int k = p[i] - j;
			int64 prev = p[i] * j + k, r = prev * p[i];
			if(!isPrime(prev)) continue;
			else if(prev * j + k > LIMIT / r) break;
			while(true) {
				prev = prev * j + k;
				if(prev > LIMIT / r || !isPrime(prev)) break;
				r *= prev;
				exp[en++] = r;
			}
		}
	sort(exp, exp+en); scanf("%d", &T);
	for(t = 0; t < T; t++) {
		int b, e; scanf("%d %d", &b, &e);
		printf("%d\n", upper_bound(exp, exp+en, e)-lower_bound(exp, exp+en, b));
	}
	
	return 0;
}

bool isPrime(int m)
{
	if(m < MAX) return prime[m];
	else {
		int i;
		for(i = 0; i < pn; i++)
			if(m % p[i] == 0) return false;
		return true;
	}
}