No.312 置換処理

Quiz

https://yukicoder.me/problems/no/312

Submit

https://yukicoder.me/submissions/336225

解法

• 解説の通り
• 素数を探すときはsqrt(N)まででいい、という定石

落とし穴

• N = 大きい素数 x 2
• のとき、解はNではなくN/2
• この問題の設定により、2で割るチェックをしていないので見落としがち

感想

• 素数を探すforループの終了条件で、最初はsqrtを使っていたが以下のように変更した

for(ll i=3; i*i<=N; i++){
        if(N%i==0){
            p(i);
            return 0;
        }
    }

• sqrtは遅い（間に合うけど）
• 最初、iの型をintにしていたら桁あふれしてしまってTLEした。long longにして解決