POJ2689 Prime distance 素数

/* 题目描述：给出长度小于1e6的区间[L , R] (1 <= L < R <=2^31)，要求输出区间内距离最远的两个素数和距离最近的 的两个素数，如果区间内不足两个素数按照题目要求输出 方法：由定理可知，“n为合数则n一定有不超过√n的素因子”，因此，可以预处理1e5以内的所有素数，在利用这些素数 对L ， R之间的数进行筛选，用vis数组记录L~R之间的每一个数是否为素数，其中用vis[i]表示i+L是否为素数的 情况。 */ #pragma warning(disable:4786) #pragma comment(linker, "/STACK:102400000,102400000") #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<stack> #include<queue> #include<map> #include<set> #include<vector> #include<cmath> #include<string> #include<sstream> #define LL long long #define FOR(i,f_start,f_end) for(int i=f_start;i<=f_end;++i) #define mem(a,x) memset(a,x,sizeof(a)) #define lson l,m,x<<1 #define rson m+1,r,x<<1|1 using namespace std; const int INF = 0x3f3f3f3f; const int mod = 1e9 + 7; const double PI = acos(-1.0); const double eps=1e-8; const int maxn = 1e5 + 5; int isprime[maxn], vis[10 * maxn]; LL prime[maxn]; int pnum ; void find_prime(int n) { pnum = 0; mem(prime, 0); mem(isprime, 1); for(int i = 2 ; i < n ; i++){ if(isprime[i]) prime[pnum++] = i; for(int j = 0; j<pnum && i * prime[j] < n ; j++){ isprime[i * prime[j] ] = 0; if(i % prime[j] == 0) break; } } } int main() { find_prime(1e5 + 2); LL L , R; while(scanf("%lld %lld",&L,&R)!=EOF){ mem(vis,1); for(LL i = 0 ; i<pnum ; i++){ if(prime[i] > R) break; LL j = L / prime[i]; while(j * prime[i] < L) ++j; if(j == 1) j = 2; for( ; j * prime[i] <= R ; j++){ vis[ j * prime[i] - L ] = 0; } } if( L == 1) vis[0] = 0; LL maxv = - INF , minv = INF , last = -1 ; LL maxx , maxy , minx , miny ; bool ok = 0; for(int i = 0 ; i<= R - L ; i++){ if(last == -1 && vis[i]) last = i; else if(last != -1 && vis[i]){ if(maxv < i - last + 1){ maxv = i - last + 1; maxx = last ; maxy = i; } if(minv > i - last + 1){ minv = i - last + 1; minx = last ; miny = i; } ok = 1; last = i; } } if(ok) printf("%lld,%lld are closest, %lld,%lld are most distant.\n",minx + L , miny + L , maxx + L , maxy + L); else printf("There are no adjacent primes.\n"); } return 0; }