Factoring

import math as m

#num을 인수분해 한 후 그 수들의 리스트를 반환(simple division)
def factoring_simple(num):
    n = 2 #처음 소수인 2부터 시작
    factors = [] #num의 소인수들
    while num != 1: #num이 1이 될 때까지 반복
        if num % n == 0: #만약 n이 num의 소인수라면
            factors.append(n) #리스트에 저장
            num /= n #num을 n으로 나눈 몫으로 변경
        else: #n이 소인수가 아니라면
            n += 1 #다음 소수로 연산을 하기 위한 증가 연산
    return factors #소인수 리스트 반환

#num = q*p를 만족하는 q, p의 값을 반환
def factoring_fermat(num):
    factors = [] #num의 2가지 소인수
    a = m.ceil(m.sqrt(num)) #num의 제곱근보다 작거나 같은 정수로 초기화
    b = a*a - num #c^2 = a^2 - num의 형태로 만들기 위한 b를 설정
    while b != m.ceil(m.sqrt(b))*m.ceil(m.sqrt(b)): #b가 제곱수가 아니라면
        a = a + 1 #다음 숫자 검사
        b = a*a - num #바뀐 a를 사용하여 b를 다시 설정
    factors = [int(a - m.sqrt(b)), int(a + m.sqrt(b))] #factors리스트를 초기화
    return factors #소인수 리스트 반환

#메인 함수
def main():
    print('factoring_simple(11):', factoring_simple(11))
    print('factoring_simple(100):', factoring_simple(100))
    print('factoring_simple(12345):', factoring_simple(12345))
    print('factoring_simple(1000001):', factoring_simple(1000001))
    print('factoring_simple(2**16):', factoring_simple(2**16))
    print('factoring_fermat(15):', factoring_fermat(15))
    print('factoring_fermat(119):', factoring_fermat(119))
    print('factoring_fermat(187):', factoring_fermat(187))
    print('factoring_fermat(2987):', factoring_fermat(2987))
    print('factoring_fermat(6750311):', factoring_fermat(6750311))

main()