URAL 2070 Interesting Numbers

PRoblem

acm.timus.ru/problem.aspx?space=1&num=2070

题意

条件1：质数

条件2：不一定是质数，但因子个数（包括1和本身）是质数的数

求 [ L , R ] 内同时满足或同时不满足两个条件的数的个数。

Analysis

先求反面：只满足其中一个条件的数的个数，然后用总数去减。

因为质数的因子个数一定是质数 2，所以反面的数就是：因子个数是质数的合数。

这样的数一定是某一个质数的某次幂（除去1次幂，因为不算质数），而且指数满足：指数+1 是一个质数。

因为将一个数进行质数分解，如果有多个质因子的幂（非0次幂），则这个数的因子数一定不是质数。举个例子，a = b^c * d^e，那么由排列组合 a 的因子个数就是：n = (c + 1) * (e + 1)个，而 n 一定不是质数，因为它至少可以拆成：(c + 1) * (e + 1)。所以一定是某一个质数的某次幂。

假如某个数 a 可以素数分解成： a = b^c，那 a 的因子个数就是 c+1 个（1，b，b^2，…，b^c），所以要求的质数幂还要其指数满足：指数+1 是质数。

可以分别算 [ 2，R ] 和 [ 2，L-1 ] 的反面的数的个数然后再相减得出 [ L，R ] 内反面的数个数。

先打个 [ 1，1e6 ] 的质数表，升序枚举质数的在范围内的幂来统计。

Source code

#include <cstdio>#include <cstring>using namespace std;const int LEN = 1000000;int p[78498], top;bool num[LEN+1];void sieve(){	top = 0;	memset(num, true, sizeof num);	for(int i=2; i<=LEN; ++i)		if(num[i])		{			p[top++] = i;			for(int j=i<<1; j<=LEN; j+=i)				num[j] = false;		}}int solve(long long n){	int cnt = 0;	// 从2次幂开始	for(int i=0, zhishu=2; i<top && p[i]<=n; ++i, zhishu=2)		for(long long j=(long long)p[i]*p[i]; j<=n; j*=p[i], ++zhishu)			if(num[zhishu+1])				++cnt;	return cnt;}int main(){	sieve();	long long l, r;	scanf("%I64d%I64d", &l, &r);	printf("%I64d/n", (r-l+1) - (solve(r)-solve(l-1)) );	return 0;}