프로그램 1.3.9 소인수 분해 (factors.py)

import sys
import stdio
 
n = int(sys.argv[1])
 
factor = 2
while factor*factor <= n:
    while (n % factor) == 0:
        # 소인수로 나눈 후 소인수를 출력한다.
        n //= factor 
        stdio.write(str(factor) + ' ')
    factor += 1
    # n의 모든 소인수는 factor보다 크거나 같다.
 
if n > 1:
    stdio.write(n)
stdio.writeln()

n
factor

분해할 부분
확인할 인수

이 프로그램은 모든 양의 정수를 소인수 분해해 출력한다. 코드는 간단하지만, 이 코드가 맞는지 확신이 들기까지는 곰곰이 생각해봐야 할 것이다.

% python3 factors.py 3757208
2 2 2 7 13 13 397
% python3 factors.py 287994837222311
17 1739347 9739789