素因数分解を高速にやるには
こんなコードを書いたけど、n以下の素数のリストを得ずに、例えば素数テストを使ってもっと早く計算できたりするのかなぁ。
# coding: utf-8 import primetable def factory(n = 10**7): ps = primetable.primelist(n) # n以下の素数をリストで返す memo = {1: []} for p in ps: memo[p] = [p] def primefactorization(n): if n in memo: return memo[n] for p in ps: if n % p == 0: pf = primefactorization(n / p) memo[n] = pf + [p] #([p] if p not in pf else []) return memo[n] return primefactorization # # factorizer = factory(100) # factorizer(10) # => [5, 5, 2, 2] # factorizer(31) # => [31] #