這題折磨我好長時間啊。 關鍵是數據范圍太大了。所以樸素的方法篩素數行不通。 因此現在[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; }
