商城网站源码,电商数据平台,品易云代理ip,c 网站开发需要学什么软件有哪些求l、r之间的质数#xff0c;范围在2e9#xff0c;但l、r的差值不大#xff0c;在1e6范围内 先求出 内的质数#xff0c;然后拿这个指数去筛[l, r]范围内的即可
#includebits/stdc.h
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl \…求l、r之间的质数范围在2e9但l、r的差值不大在1e6范围内 先求出 内的质数然后拿这个指数去筛[l, r]范围内的即可
#includebits/stdc.h
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl \nusing namespace std;typedef pairint, int PII;
typedef long long ll;
typedef long double ld;const int N 50010, M 1000010;int primes[N], cnt;
bool st[M];
int p[M];void init()
{for(int i 2; i N; i ){if(!st[i])primes[cnt ] i;for(int j 0; primes[j] * i N; j ){st[primes[j] * i] true;if(i % primes[j] 0)break;}}
}int main()
{IOSinit();int cnt_tmp cnt;ll l, r;while(cin l r){if(l 1)l 2;memset(st, false, sizeof st);cnt cnt_tmp;for(int i 0; i cnt; i ){ll start max((ll)primes[i] * 2, (l primes[i] - 1) / primes[i] * primes[i]);for(ll j start; j r; j primes[i]){st[j - l] true;}}cnt 0;for(int i 0; i r - l; i ){if(!st[i])p[cnt ] i;}if(cnt 2){cout There are no adjacent primes. endl;continue;}int min1 0, min2 2e9, max1 0, max2 0;for(int i 0; i cnt - 1; i ){if(p[i 1] - p[i] min2 - min1){min1 p[i];min2 p[i 1];}if(p[i 1] - p[i] max2 - max1){max1 p[i];max2 p[i 1];}}cout min1l , min2l are closest, max1l , max2l are most distant. endl;}return 0;
}
要注意的几个点
1.对于每次筛最少要从primes[i] * 2开始不能筛到质数
2.在start计算过程中和j的过程中很容易爆int注意这部分开ll
3.求大于等于l的第一个p的倍数(l p - 1) / p * p
