素因数分解

割り切れるかどうか試してみる、という力業の方法で。

http://tsumuji.cocolog-nifty.com/tsumuji/2009/05/post-af3f.html を参考に作成。素因数分解は素数で割ってみることでできる。しかし、素数を求めることそのものに時間がかかるため単に 2 と 3 以上の奇数で割ってみてしまったほうが早い、そして 2, 3 と 6 * n ± 1 (n は 1 以上の整数）で割ったほうがさらに早い、という内容。

factorize.py

# coding: utf-8

u"""素因数分解"""

import itertools

def _ifactorize_p():
    u"""2, 3, および素数の可能性がある奇数 p = 6 * n ± 1"""

    yield 2
    yield 3
    num = 1
    for add in itertools.cycle((4, 2)):
        num += add
        yield num

def ifactorize(num):
    u"""素因数分解
    
    素因数を小さい順に一つずつ返すイテレータ。"""

    num = int(num)
    if num < 1:
        raise ValueError(u'%d is not positive number' % num)
    elif num == 1:
        yield 1
        return

    for fact in _ifactorize_p():
        if num < fact ** 2:
            if num > 1:
                yield num
            break
        q, r = divmod(num, fact)
        while not r:
            num = q
            yield fact
            q, r = divmod(num, fact)

def factorize(num):
    u"""素因数分解
    
    素因数をまとめた tuple を返す
    
    >>> factorize(360)
    (2, 2, 2, 3, 3, 5)
    """

    return tuple(ifactorize(num))

def ifactorize_groupby(num):
    u"""素因数分解
    
    素因数とこれが含まれる数の組を順次返すイテレータ。"""

    for prime, g in itertools.groupby(ifactorize(num)):
        #c = 0
        for c, _ in enumerate(g, 1):
            pass
        yield prime, c

def factorize_groupby(num):
    u"""素因数分解
    
    素因数とこれが含まれる数の組をまとめたタプルを返す。
    
    >>> factorize_groupby(360)
    ((2, 3), (3, 2), (5, 1))
    """

    return tuple(ifactorize_groupby(num))

def main():
    import os
    import sys
    from optparse import OptionParser

    usage = '%prog integer_number [...]\nex: %prog 360'
    parser = OptionParser(usage=usage)
    parser.add_option('-g', '--groupby',
            action='store_true', dest='groupby')
    parser.set_defaults(groupby=False)
    options, args = parser.parse_args()

    if len(args) < 1:
        parser.print_help()
        parser.exit()

    f = factorize_groupby if options.groupby else factorize
    for arg in args:
        try:
            num = int(arg, 10)
            print '%d: %s' % (num, f(num))
        except ValueError, e:
            print e

if __name__ == '__main__':
    main()

実行結果

>factorize.py 360
360: (2, 2, 2, 3, 3, 5)

>factorize.py --groupby 360
360: ((2, 3), (3, 2), (5, 1))