방법은 단순히 몇 개의 소수들로 일단 나눈 뒤, 그 이후에는 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.
혹시 이것보다 더 좋은 알고리즘이 있다면 나중에 코딩해봐야겠다.
댓글 없음:
댓글 쓰기