题意:筛一段区间内素数的个数,区间宽度10w,区间范围INT_MAX
分析:用sqrt(INT_MAX筛一遍即可),注意先筛下界,再筛上届,因为有可能包含
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
#include <cstdio> #include <iostream> #include <ctime> #include <vector> #include <cmath> #include <map> #include <queue> #include <algorithm> #include <cstring> using namespace std; typedef long long LL; const int N=1e7+5; const int INF=0x3f3f3f3f; int cnt; bool v[N]; LL prime[700000]; void getprime(){ for(int i=2;i*i<=N-5;++i) if(!v[i]) for(int j=i*i;j<=N-5;j+=i) v[j]=1; for(int i=2;i<=N-5;++i) if(!v[i])prime[++cnt]=i; } int ans; vector<LL>g,c; bool vis[100]; void dfs(int pos,LL res){ if(pos==g.size()){ int tmp=1; for(int i=0;i<g.size();++i){ if(vis[i])continue; tmp*=(c[i]+1); } ans+=tmp; return; } dfs(pos+1,res); vis[pos]=1; for(LL i=1,k=g[pos];i<=c[pos];++i,k*=g[pos]) dfs(pos+1,res*k); vis[pos]=0; return; } int main() { getprime(); int cas=0,T; scanf("%d",&T); while(T--){ LL t,n; scanf("%lld",&n),t=n; g.clear(),c.clear(); for(int i=1;i<=cnt&&prime[i]*prime[i]<=t;++i){ if(t%prime[i])continue; int tot=0; g.push_back(prime[i]); while(t%prime[i]==0)t/=prime[i],++tot; c.push_back(tot); } if(t>1)g.push_back(t),c.push_back(1); ans=0; dfs(0,1); printf("Case %d: %d ",++cas,(ans>>1)+1); } return 0; }