LightOJ 1197 Help Hanzo 素数筛

题意：筛一段区间内素数的个数，区间宽度10w，区间范围INT_MAX

分析：用sqrt(INT_MAX筛一遍即可)，注意先筛下界，再筛上届，因为有可能包含

#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;
}