2397.cpp

哈尔滨工业大学ACM 竞赛网上在线试题集锦的源代码

/* This Code is Submitted by wywcgs for Problem 2397 on 2006-10-10 at 16:11:38 */
#include <cstdio>
#include <algorithm>
using namespace std;

typedef long long int64;
const int N = 1 << 20, PN = 300000;

bool prime[N], semp[N];
int p[PN], pn = 0, sp[N], spn = 0;

int main()
{
	int n;
	memset(prime, true, sizeof(prime));
	memset(semp, false, sizeof(semp));
	for(int i = 5; i < N; i += 4) {
		if(!prime[i]) continue;
		p[pn++] = i;
		for(int j = 5*i; j < N; j += 4*i) prime[j] = false;
	}
	for(int i = 0; i < pn; i++)
		for(int j = i; j < pn; j++) {
			int64 r = (int64)p[i]*p[j];
			if(r >= N) break;
			else if(semp[r]) continue;
			sp[spn++] = r; semp[r] = true;
		}
	sort(sp, sp+spn);
	while(scanf("%d", &n) != EOF && n != 0) {
		printf("%d %d\n", n, upper_bound(sp, sp+spn, n)-sp);
	}

	return 0;
}