파이썬 소인수 분해(또는 소수 판단)

Project Euler 12 번을 풀다가 소인수 분해 알고리즘이 필요해서 작성하게 되었다.

방법은 단순히 몇 개의 소수들로 일단 나눈 뒤, 그 이후에는 2씩 더해서 수를 모두 나눠서 사전 객체로 반환하도록 했다.

#!/usr/bin/env python3
# Copyright (C) 2010년 bluekyu (http://bluekyu.textcube.com/)
# 이 프로그램은 자유 소프트웨어입니다. 소프트웨어의 피양도자는 자유 소프트웨어 재단이 공표한
# GNU 일반 공중 사용 허가서 2판 또는 그 이후 판을 임의로 선택해서, 그 규정에 따라 프로그램을 개작하거나 재배포할 수 있습니다.
# 이 프로그램은 유용하게 사용될 수 있으리라는 희망에서 배포되고 있지만, 특정한 목적에 맞는 적합성 여부나 판매용으로 사용할 수
# 있으리라는 묵시적인 보증을 포함한 어떠한 형태의 보증도 제공하지 않습니다. 보다 자세한 사항에 대해서는 GNU 일반 공중 사용 허가서를 참고하시기 바랍니다. 

def factor(n) :
    if n <= 0 :
        return {}
    f = {}
    for k in [2,3,5,7,11,13,17,19,23,29,31,37,41] :
        while not (n % k) :
            f[k] = f.setdefault(k, 0) + 1
            n //= k
    while n != 1 :
        if k > n**0.5 :
            f[n] = 1
            break
        while not (n % k) :
            f[k] = f.setdefault(k, 0) + 1
            n //= k
        k += 2
    return f

if __name__ == '__main__' :
    import sys
    try :
        print(factor(int(sys.argv[1])))
    except :
        print("Input value, {} is invalid".format(sys.argv[1]))

ps.
이것을 작성한 후에, k 가 2씩 더해지면서 나오는 수들중에서 이미 알고 있는 소수들로 나누어지는 경우를 제외하는 코드를 넣어봤는데, 오히려 시간이 더 걸린다. 그냥 2씩 쭉 더해가는 것이 훨씬 빠르다.

ps2.
혹시 이것보다 더 좋은 알고리즘이 있다면 나중에 코딩해봐야겠다.