素因数分解したかった

prime_decomposition.py

import math
def prime_decomposition(n):
  array = []
  primes = primetable(int(math.ceil(math.sqrt(n))))
  while n > 1:
    for p in primes:
      if n % p == 0:
        n /= p
        array.append(p)
        break
    else:
      array.append(n)
      break
    
  return array

def primetable(max):
  sq = math.sqrt(max)
  table = []

  t = range(0, max+1)
  t[0] = 0
  t[1] = 0
  p = 2
  while p <= sq:
    if t[p] != 0:
      j = p + p
      while j <= max:
        t[j] = 0
        j += p
    p += 1
  for p in t:
    if p != 0:
      table.append(p)
  return table

if __name__ == '__main__':
  print prime_decomposition(14)

(1) for p in primes は外側に出したほうがいいです。こんな感じ。

for p in primes:
    if n == 1:
        break
    while n % p == 0:
        n /= p ; array.append(p)
if n > 1:
    array.append(n)

今（Revision 3）のコードだと、たとえば 103 で割った後、while ループの次のステップで、また 2 から順番に割り切れるかどうかを調べることになる（けれども実際には 103 より小さい数で割り切れることはない）ので、ちょっと効率が悪いです。

(2) 実を言うと、素数一覧をいちいち作らないで、

factors = []
p = 2
while p * p <= n:
    while n % p == 0:
        n /= p ; factors.append(p)
    p += 1
if n >= 2:
    factors.append(n)

で十分だったりします。factors に 4 とか 6 とかが入らないか心配になるかもしれないけれど、p = 4 とか p = 6 になったときには、その手前にある 2 とか 3 とかで割れるだけ割られているので、n はすでに 4 とか 6 とかでは割り切れない数になっています。計算効率的にも問題ないはずです（エラトステネスのふるいだって O(max) 時間はかかるので）。

yuizumi
おおお、ありがとうございます(´；ω；｀)
ちゃんと直してみたいと思います！！！