結果

問題 No.371 ぼく悪いプライムじゃないよ
コンテスト
ユーザー 🍡yurahuna
提出日時 2016-05-12 16:15:01
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,339 bytes
コンパイル時間 1,704 ms
コンパイル使用メモリ 170,828 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-10-05 13:59:15
合計ジャッジ時間 2,988 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3 WA * 1
other AC * 16 WA * 25 RE * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

#define rep(i,n) for (int i=0;i<(n);i++)
#define rep2(i,a,b) for (int i=(a);i<(b);i++)
#define rrep(i,n) for (int i=(n)-1;i>=0;i--)
#define rrep2(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define all(a) (a).begin(),(a).end()

typedef long long ll;
typedef pair<int, int> P;

// 誤解法 1
// mがp未満の素数で割れる場合を考慮していない

const int INF = 1e10;

vector<int> prime;
void setPrime(int n) {
    vector<bool> alive(n, true);
    alive[0] = alive[1] = false;
    rep2(i, 2, n + 1) {
        if (alive[i]) {
            prime.emplace_back(i);
            for (int j = 2 * i; j <= n; j += i) {
                alive[j] = false;
            }
        }
    }
}

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

    int L, H;
    cin >> L >> H;

    // sqrt(H)以下の素数を列挙
    setPrime(sqrt(H) + 5);

    // 「最小の素因数 p」について全探索
    int ans = -1;
    int max_min_primefactor = -1;
    for (auto p : prime) {
        if (p * p > H) break;
        int m = H / p;
        if (p * m < L) continue;
        ans = p * m;
        max_min_primefactor = p;
    }
    assert(L <= ans && ans <= H);
    assert(max_min_primefactor > 0);

    cout << ans << endl;

}
0