自然数 N を素因数分解するプログラムの作成課題。
014 - Factorization
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
atcoder.jp
考え方は合っていたのですが、実装がマズかった。
修正後の自分のコード
https://github.com/men100/math-algorithm-book/commit/e189f4e7ce470d6d911b0d30b8dbdd1052d46ad7
1. 引数を int にしてしまっていた (大きい N のとき、正しい結果が出ない)
ジャッジで AC と WA がまばらに出ていたのでおかしいなあと思っていたら、これだった。大ポカですね。
引数を long long に変えることで AC 出ました。
https://atcoder.jp/contests/math-and-algorithm/submissions/28995269
2. 毎回 2 から判定し直していた (パフォーマンスに影響)
割り切れる数に当たったら、その数で割ることを繰り返し、割り切れなかったら次はその次の値で試していくのが本課題のキモです。でも自分は毎回 2 から割り切れるか試してました。大きい N のときは結構パフォーマンスに影響あったろうなあ。
コメント