题解：P17733 [ICPC 2019 Xuzhou R] <3 numbers

· · 题解

:::info[题目分析]{open} 这个神秘的 <3 数，就是因数个数 <3 的数，包括：

分析完毕，我们令 R - L + 1 = len，即区间长度为 len。由于 1\sim 100 只有 25 个质数，而数字越大，质数的占比越小，所以就算选 1\sim 100，质数个数也不到区间长度的 \frac{1}{3}，所以可以特判掉。

:::success[Code]

#include <bits/stdc++.h>
#define ll long long
using namespace std;

inline bool is (int x) { //试除法
    if (x == 2) return 1; //特判
    for (int i = 2; i * i <= x; i ++) {
        if (x % i == 0) return 0;
    }
    return 1;
}

int main () {
    cin.tie(nullptr) -> ios::sync_with_stdio(false);
    int T; cin >> T;
    int l, r;
    while (T --) {
        cin >> l >> r;
        ll len = r - l + 1; //区间长
        if (len >= 100) { //精髓，特判掉区间长大于100的情况
            puts("Yes");
            continue;
        }
        ll ans = 0;
        for (int i = l; i <= r; i ++) { //暴力枚举
            if (i == 1 || is(i)) ans ++;
            //注意可以为1
        }
        if (ans * 3 < len) { //乘法不至于损耗精度
            puts("Yes");
        }
        else puts("No");
    }
    return 0;
}

:::