题目链接http://acm.timus.ru/problem.aspx?space=1&num=2070
题意：给定区间L R，求条件二者都满足，或者都不满足的数字有多少个。
条件1：素数 ，条件2：因子的个数是素数。
思路： 正向来找非常难找，反向来看。只要是素数，两者条件都满足。合数的话，不满足条件1，再找出满足条件2的，用总数R-L+1减去这个数即可。
关键是因子的个数是素数，这个怎么来找呢。
假设一个数字可以被分解成 X = p1^a+p2^b 形式，p1,p2都是素因子，ab为指数
那么这个数的因子是 p1,p1*p1,...,p1^a (p1组合) ,p2,p2*p2,...,p2^b（p2组合）, p1^p2,p1*p2^2,...p1^a*p2^b（p1和p2组合）,总数是 a+b+a*b+1个因子，即(a+1)*(b+1) ，三个素因子的时候 (a+1)*(b+1)*(c+1)
所以，只有当不同的素因子的个数为1的时候，并且指数+1为素数的时候，才是满足的。再用总数减掉即可。
#include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<iostream> #include<vector> using namespace std; typedef long long LL; const int maxn = 1e6+10; vector<int> v; int vis[maxn]; void init() { vis[1] = 1; for ( int i=2; i<maxn; i++ ) { if ( vis[i]==0 ) { v.push_back(i); for ( int j=i+i; j<maxn; j+=i ) vis[j] = 1; } } } int main(){ init(); LL l,r; cin>>l>>r; LL ans = r-l+1; for ( int i=0; i<v.size(); i++ ) { LL cur = 1 ; int sum = 0 ; if ( v[i]*v[i]>r ) break; while ( cur<l ) { cur *= v[i]; ++sum; } while ( cur<=r ) { if ( sum>1 && vis[sum+1]==0 ) --ans; cur *= v[i]; ++sum; } } cout<<ans<<endl; return 0; }