Hoj 2276 Count prime
这题折磨我好长时间啊。关键是数据范围太大了。所以朴素的方法筛素数行不通。
因此现在[1,500000]范围内筛素数，因为[1,2147483647]范围内的合数的质因子肯定在[1,500000]范围内，再由此范围的素数淘汰掉以此素数为质因数的合数即可。
用于用到prim[i]*prim[i]范围会超int,所以一律改为long long 吧。否则会Runtime Error (SIGSEGV)
详见代码注释：
[cpp]
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
using namespace std;
#define N 500000
long long prim[500010];
long long visited[500010];
long long rank[500010];
long long flag[1000100];
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
#endif
long long l,r;
while(scanf(" %lld %lld",&l,&r) == 2)
{
long long num = 0;
memset(visited,0,sizeof(visited));
memset(rank,0,sizeof(rank));
memset(flag,0,sizeof(flag));
//求出[1,N]范围内的质数，这些质数将有可能成为[1,2147483647]范围内的质因子
//用线性筛法筛选素数
for(long long i=2; i<=N; i++)
{
if(visited[i] == 0)
{
prim[num++] = i;
}
for(long long j=0; j<num && prim[j]*i<=N; j++)
{
visited[prim[j]*i] = 1;
if(i%prim[j] == 0)
{
break;
}
}
rank[i] = num;
}
long long ans = 0;
//如果[l,r]在[1,N]范围内
if(r<=N)
{
printf("%lld\n",rank[r] - rank[l-1]);
continue;
}
//计算[l,N]范围内的质数个数
if(l<=N)
{
ans += rank[N] - rank[l-1];
l = N + 1;
}
//计算[l,r]范围内质数个数，l>N>=prim[i]
//方法是排除合数，[1,2147483647]范围内合数的质因子必定在prim[]数组中
//为避免数组越界，减去l做平移
//由于prim[i]*prim[i]可能会超出int精度，都用long long 吧
for(long long i=0;prim[i] * prim[i]<=r;i++)
{
long long start = 0;
//start为最接近l的，以prim[i]为质因子的合数
if(l%prim[i] == 0)
{
start = l;
}
else
{
start = (l/prim[i]+1)*prim[i];
}
//将[l,r]范围内的以prim[i]为质因子的合数全部标记
for(;start<=r;start+=prim[i])
{
flag[start-l] = 1;
}
}
for(long long i=l;i<=r;i++)
{
if(flag[i-l] == 0)
{
ans++;
}
}
printf("%lld\n",ans);
}
return 0;
}
补充：软件开发 , C++ ,
