素因数分解(コードジェネレータ版)

30分プログラム、その591。もういっかい素因数分解をやってみる。
id:Gemma:20090523で「おめー書いたエラトステネスの篩は遅すぎるぜー」と言われてしまった。
OK、そんなに速度のことを言うんだったら、素数を定数として埋めこんでやんよ。
でも、手で書くのは面倒だから、初回実行時に動的に生成してみた。英語で言うとコードジェネレーション。

使い方

$ python fact.py 42
[2, 3, 7]
$ python fact.py 84
[2, 2, 3, 7]

ソースコード

#! /usr/bin/python
# -*- mode:python; coding:utf-8 -*-
#
# fact.py -
#
# Copyright(C) 2009 by mzp
# Author: MIZUNO Hiroki / mzpppp at gmail dot com
# http://howdyworld.org
#
# Timestamp: 2009/05/24 20:36:12
#
# This program is free software; you can redistribute it and/or
# modify it under MIT Lincence.
#

import sys
import os.path
def sieve(xs):
    if xs == []:
        return []
    else:
        x  = xs[0]
        return [x] + sieve([y for y in xs if y % x != 0])

def div_count(x,y,count):
    if x % y == 0:
        return div_count(x / y ,y,count+1)
    else:
        return count

def primes(n):
    return sieve(xrange(2,n))

if os.path.exists('primes.py'):
    io = file('primes.py','w')
    io.write("primes = %s" % str(primes(1000)))
    io.close()

def fact(n,primes):
    for p in primes:
        count = div_count(n,p,0)
        if count != 0:
            for i in xrange(0,count):
                yield p

mod = __import__('primes')

if __name__ == '__main__':
    for arg in sys.argv[1:]:
        n = int(arg)
        if n < 1000:
            print list(fact(n,mod.primes))
        else:
            print list(fact(n,primes(n)))

参考

• 過去の30分プログラム