エントリーの編集
エントリーの編集は全ユーザーに共通の機能です。
必ずガイドラインを一読の上ご利用ください。
Pythonで高速素因数分解〜競プロ用〜 - Qiita
記事へのコメント0件
- 注目コメント
- 新着コメント
このエントリーにコメントしてみましょう。
注目コメント算出アルゴリズムの一部にLINEヤフー株式会社の「建設的コメント順位付けモデルAPI」を使用しています
- バナー広告なし
- ミュート機能あり
- ダークモード搭載
関連記事
Pythonで高速素因数分解〜競プロ用〜 - Qiita
1. はじめに どうも〜、AtCoder修行中のsnowです。ABC110:D-Factorizationという問題の中で、素因数分... 1. はじめに どうも〜、AtCoder修行中のsnowです。ABC110:D-Factorizationという問題の中で、素因数分解を行う場面があったので、その際に書いたコードをちょっとばかり改変して共有します。 「整数 $N$ の素因数の最大値は高々$\sqrt{N}$以下になる」という性質を利用して、$O(\sqrt{N})$で計算できるように実装していますので、大体の問題には対応できるはずです(多分、、、)。 詳細については、Wikipedia (試し割り方)を確認してください。 2. コード """nを素因数分解""" """2以上の整数n => [[素因数, 指数], ...]の2次元リスト""" def factorization(n): arr = [] temp = n for i in range(2, int(-(-n**0.5//1))+1): if temp%i=