线性筛爆了!QwQ
  • 板块学术版
  • 楼主Womind
  • 当前回复2
  • 已保存回复2
  • 发布时间2023/10/13 20:01
  • 上次更新2023/11/2 14:04:42
查看原帖
线性筛爆了!QwQ
801322
Womind楼主2023/10/13 20:01

开1e5还好好的,1e6就RE我的数组都是同步的为什么会ER。 求助大佬Orz

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b)  for (int i = (a); i <= (b); i++)
#define repe(i,a,b) for (int i = (a); i >= (b); i--)
const int N = 1e6 + 10;
int l, r, cnt = 0, a[N]; 
bool vis[N], vt[N];
int d[N];
void sieve() {
	int q = 1e6 - 1;
	rep(i,2,q) {
		if (!vis[i]) d[++cnt] = i;
		for(int j = 1; j * i <=q && j <= cnt; j++) {
			vis[i * d[j]] = 1;
			if (i % d[j] == 0) break;
		}
	}
}
int main(){
	sieve(); // sieve 外移当预处理 
	while(scanf("%d%d", &l, &r) != EOF) {
		memset(vt, 0 , sizeof (vt));
		int q = sqrt(r);
		rep(i,1,cnt) {
			if ( d[i] > q) break;
			int g = 2;
			while(g * d[i] < l) g++;
			for(; g * d[i] <= r; g ++) {
				vt[g * d[i] - l] = 1;
			}
		}
		int x = 0, minx = 0x7fffffff, maxx = 0, mina, minb, maxa, maxb;
		rep(i,0,r - l) {
			if (!vt[i]) {
				if (x != 0) {
					if(i + l - x < minx) minx = min(minx, i + l - x), mina = x, minb = i + l;
					if(i + l - x > maxx) maxx = max(maxx, i + l - x), maxa = x, maxb = i + l;
				}
				x = i + l;
			}
		}
		if (minx == 0x7fffffff ) {
			printf("There are no adjacent primes.\n");
		} else printf("%d,%d are closest, %d,%d are most distant.\n", mina, minb, maxa, maxb);
	}
}
2023/10/13 20:01
加载中...