perogram

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にして解決