AcWing 3529. 连续合数段
原题链接
简单
作者:
王小强
,
2022-04-02 09:56:02
,
所有人可见
,
阅读 240
直觉
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define not !
#define and &&
#define or ||
#define ri register int
#define rep(inc, frm, to) for (ri inc = frm; inc < (to); ++inc)
#define rep2(inc, frm, to) for (ri inc = frm; inc > (to); --inc)
typedef long long int ll;
#define r() fast_read()
ll fast_read(void) {
ll n = 0, sign = 1;
char c = getchar();
while (c < 48 or c > 57) {
if (c == '-') sign = ~0;
c = getchar();
}
while (c >= 48 and c <= 57) {
n = (n << 1) + (n << 3) + (c ^ 48);
c = getchar();
}
return sign * n;
}
bool isprime(int x) {
if (x <= 1) return false;
for (int i = 2; i * i <= x; ++i)
if (not(x % i)) return false;
return true;
}
signed main(int argc, char const *argv[]) {
int a = r(), b = r(), l = -1, r = -1, ansl = -1, ansr = -999;
bool prev = 0;
for (int i = a; i <= b; ++i) {
if (isprime(i)) {
if (not prev) continue; // 前面一个数也是质数
if (l != -1 and r != -1) {
if (r - l > ansr - ansl) ansl = l, ansr = r;
}
prev = 0;
} else { // 是合数
if (prev) ++r; // 前一个数也是合数
else l = r = i;
prev = 1;
}
}
if (r - l > ansr - ansl) ansl = l, ansr = r;
rep(i, ansl, ansr + 1) printf("%d ", i);
return ~~(0 ^ 0);
}