//P以上の素数を使って出来る合成数はP^2以上になる。 //[1, 10^8]のとき…10000以下の素数の最大値を2乗したものが答え -> ウソでした。素数の最大値 * 素数の最大値を超える素数 <= 10^8を満たす数が答え。厳しい。 //[L, R]のとき…√R以下の素数の最大値Pが√L以上ならP^2が答え。-> ウソでした。QをP+1以上の素数とすると、PQ <= √Rを満たすPQの最大値が答え。厳しかった。 //√L未満なら、10^5以下の素数で[L, R]に対して区間篩を行えば間に合いそう。[L, R]の大きさが数百万になっているため。 #include #include #define int long long using namespace std; int l, r; int prime[100000], primeNum; //n以下の素数をprime[]に入れて、入れた個数を返す int setPrime(int n, int prime[]) { bool isPrime[100100]; int i, j; int ret = 0; for (i = 2; i <= n; i++) isPrime[i] = true; isPrime[0] = false; isPrime[1] = false; for (i = 2; i <= n; i++) { if (isPrime[i]) { for (j = i * 2; j <= n; j += i) { isPrime[j] = false; } } } for (i = 0; i <= n; i++) { if (isPrime[i]) { prime[ret++] = i; } } return ret; } signed main() { int l, r; int i, j; cin >> l >> r; primeNum = setPrime(100100, prime); for (i = primeNum - 1; i >= 0; i--) { if (prime[i] * prime[i] <= r) { break; } } if (prime[i] * prime[i] >= l) { for (j = i + 1; prime[i] * prime[j] <= r; j++); j--; cout << prime[i] * prime[j] << endl; return 0; } //ここまでで、prime[i]^2 < L <= R < prime[i+1]^2が確定しているので、[L, R]が小さい。よって、区間篩します。 static bool isPrime[12000000]; //isPrime[i] = L + iが素数ならtrue, 合成数ならfalse int ans = -1; for (i = 0; i <= r - l; i++) { isPrime[i] = true; } for (i = 0; i < primeNum; i++) { for (j = prime[i] * ((l + prime[i] - 1) / prime[i]); j <= r; j += prime[i]) { //cout << prime[i] << " " << j << endl; if (isPrime[j - l] && j != prime[i]) { isPrime[j - l] = false; ans = j; } } } cout << ans << endl; return 0; }