vs Chick

2 secs 1024 MB

dyktr_06

問題

提出

テストケース

解説

明らかに $A$ 以下で最も大きい素数を選ぶことが最適です。

ある数 $N$ が素数かどうかを判定するには、平方根まで順に割って確かめることにより $O(\sqrt{N})$ で判定することができます。

素数定理より、 $A$ から順に素数の判定を行うことで $O(\sqrt{A} \log A)$ で $A$ 以下で最も大きい素数を求めることができ十分に高速です。

実装例(C++)

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

template <typename T>
bool isPrime(T n){
    switch(n){
        case 0: // fall-through
        case 1: return false;
        case 2: return true;
    }

    if(n % 2 == 0) return false;

    for(T i = 3; i * i <= n; i += 2){
        if(n % i == 0){
            return false;
        }
    }
    return true;
}

int main(){
    int h, a; cin >> h >> a;
    int ans = 0;
    for(int i = a; i >= 2; i--){
        if(isPrime(i)){
            ans = (h + i - 1) / i;
            break;
        }
    }
    cout << ans << "\n";
}