소인수 분해

### 소인수 분해 ###

: 합성수를 소수의 곱으로 나타내는 방법

(위키백과 https://mathbang.net/200)

 

인수

: 어떤수를 만들 때 곱해지는 각각의 것들(약수, a=b×c이면 b, c를 a의 인수)

​

소인수

: 인수(약수) 중에서 소수인 것들

​

 

#x는  줄여가면서 소인수는 늘려가면서 x를 소인수로 나눠 준다.

def prime(x):
    p = 2 #소인수의 시작
    factorization = [] #소인수를 저장하는 곳
	
	# 시간 복잡도가 x ** 0.5일 때만 파악 
	# 소인수를 점점 늘려가면서 계산 
	while p ** 2 <= x: 
        if x % p == 0:
            x //= p 
            factorization.append(p)
        else:
            p += 1 

	#1을 제외한 자기자신도 인수가 될 수 있기 때문
    if x > 1:
        factorization.append(x)
        
    return fac