首页 > 代码库 > POJ2689 Prime Distance
POJ2689 Prime Distance
题意:输入[l,r]代表,问区间里面最近和最远的两个素数(0<l<r<int_max, r-l<100000)
题解:素数筛,一个数是合数,那么它存在小于sqrt(n)的素因子,找到所有小于sqrt(int_max)的素数,注意数据:1 2
#include <iostream>#include <string.h>#include <stdio.h>#define N 1001000#define ll long longusing namespace std;bool isprime[N], isp[N];long long prime[N], num, ans[N];void doprime(long long n){ long long i,j; num = 0; memset(isprime, true,sizeof(isprime)); isprime[1] = 0; for(i=2;i<=n;i++){ if(isprime[i]){ prime[num++] = i; for(j=i*i;j<=n;j+=i) isprime[j] = false; } }}void doprime2(long long l,long long r){ memset(isp, true, sizeof(isp)); for(long long i=0;i<num;i++){ long long t = l/prime[i]; while(prime[i]*t<l||t<=1) t++; for(long long j=t*prime[i];j<=r;j+=prime[i]) isp[j-l] = 0; } if(l==1) isp[0] = 0;}int main(){ long long ansl,ansr, l, r, ansll, ansrr; doprime(50000); while(cin>>l>>r){ doprime2(l,r); long long t = 0; for(long long i=l;i<=r;i++) if(isp[i-l] == 1) ans[t++] = i; if(t < 2) printf("There are no adjacent primes.\n"); else{ long long mi = 10000000, ma = -10000000; for(long long i=0;i<t-1;i++){ if(mi>ans[i+1]-ans[i]){ ansl = ans[i]; ansr = ans[i+1]; mi = ansr-ansl; } if(ma < ans[i+1]-ans[i]){ ansll = ans[i]; ansrr = ans[i+1]; ma = ans[i+1]-ans[i]; } } printf("%lld,%lld are closest, %lld,%lld are most distant.\n", ansl, ansr, ansll, ansrr); } }}
POJ2689 Prime Distance
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。