#include #include #include #include #include #include #include #include #include #include #include //INT_MIN/MAX using namespace std; #define FOR(i,s,e) for(int (i)=(s);(i)<(e);(i)++) #define FORR(i,s,e) for(int (i)=(s);(i)>(e);(i)--) #define MOD 1000000007 #define llong long long #define debug(x) cout<<#x<<": "<> L >> H; int n = sqrt(H); vector prime; vector a; a.resize(H + 1); FOR(i, 0, H + 1) a[i] = 1; /* √High 以下の素数リスト生成 */ for (int s = 2; s <= n; s++) { if (a[s] == 1) { for (long j = 0; s*(j + 2) <= H; j++) { a[s*(j + 2)] = 0; } } } FOR(i, 1, n + 1) if (a[i]) { prime.push_back(i); debug(i); } debug(prime.size()); FORR(i, prime.size() - 1, -1) {//答えが大きい数字を選択するので上から見る 10^4 改善不可 if (prime[i] * prime[i] <= H)//地味だった debug(prime[i]); for (long long int j = H / prime[i]; j >= L / prime[i]; j--) { //ゴミの取り除き方がわからない // 10^5 だったのでここは改善しなければならない bool f = true; for (int p = i - 1; p >= 0; p--) {//現在の素数以下の素数でわりきれればそれは答えではない if (p != 0 && j%prime[p] == 0) { f = false; break; } } if (i == 1)//復活の儀、最悪 f = true; if (f == true && L <= j*prime[i] && H >= j*prime[i]) { return 0; } } } return 0; }