二次筛法
題目：http://poj.org/problem?id=2689
?
分析：本題數據區間的上界達到21億，不能將所有小于21億的素數存下來，只能針對本題的假設：區間長度小于1000000，把給定區間[ L,U ]的所有素數通過篩法找出來，使用篩法篩掉[L,U]區間的所有非素數，需要知道[L,U]區間的所有非素數的素數因子（因為一個非素數是被它的最小素數因子篩掉），2147483647內的數或者是素數，或者能被sqrt(2147483647)內的素數整除，也就是說，[L,U]區間的所有非素數的素數因子都在sqrt(2147483647)內，預先將sqrt(2147483647)內的所有素數找出來，然后用這些素數去篩掉指定區間的所有非素數。
?
代碼：
#include <stdio.h> #include <string.h> #define N 50001 #define INF 99999999 long long prime1[N+2],nprime1; bool isprime[20*N+2]; void make_prime1() {long long i,j;nprime1=0;memset(isprime,1,sizeof(isprime));for(i=2;i<N;i++){if(isprime[i]){nprime1++;prime1[nprime1]=i;for(j=i*i;j<N;j+=i){isprime[j]=0;}}} } long long L,U; long long prime2[1000001]; long long nprime2; void make_prime2() {long long i,j,b;memset(isprime,1,sizeof(isprime));for(i=1;i<=nprime1;i++){b=L/prime1[i];while(b*prime1[i]<L||b<=1)b++;for(j=b*prime1[i];j<=U;j+=prime1[i]){if(j>=L){isprime[j-L]=0;}}if(L==1){isprime[0]=0;}} }void solve() {long long i;long long min=INF,max=-INF;long long minl,minr,maxl,maxr;make_prime2();nprime2=0;for(i=0;i<=U-L;i++){if(isprime[i]){nprime2++;prime2[nprime2]=i+L;}}if(nprime2<=1){printf("There are no adjacent primes.\n");}else{for(i=1;i<nprime2;i++){if(prime2[i+1]-prime2[i]<min){min=prime2[i+1]-prime2[i];minl=prime2[i];minr=prime2[i+1];}if(prime2[i+1]-prime2[i]>max){max=prime2[i+1]-prime2[i];maxl=prime2[i];maxr=prime2[i+1];}}printf("%I64d,%I64d are closest, %I64d,%I64d are most distant.\n",minl,minr,maxl,maxr);} } int main() {make_prime1();while(~scanf("%I64d%I64d",&L,&U)){solve();}return 0; }
?
總結
