소인수분해

소인수(Prime Factor)

약수(인수)중에서 소수인 숫자를 소인수라고 한다.(소(수) + 인수)

파이썬으로 소인수분해 해보기

inputNum=int(input('정수 입력: '))

num=2
while num<=inputNum:
    if inputNum%num==0: # 소수찾기
        print(num)
        inputNum/=num # 찾은 소수로 나누고 그 수부터 다시 해보기
    else:
        num+=1 # 0이 아닌경우, 다음 소수를 찾아서 반복문 해보기, 파이썬에는 num++이 없다.

 

Q. 정수에 x를 곱하면 y의 제곱이 된다고 했을 때, x에 해당하는 가장 작은 정수를 구해보자.

소인수분해 요소중 홀수개인 요소만 곱해주면 된다.(12 = 2^2 * 3 이면 3이라는 뜻) list를 이용해보자.

 

inputNum=int(input('정수 입력: '))

num=2
soinsulist=[]

while num<=inputNum:
    if inputNum%num==0:
        print(num)
        inputNum/=num
        if(soinsulist.count(num)==0): soinsulist.append(num) # 홀수개인 경우만 리스트에 담기
        else: soinsulist.remove(num) # 리스트에 담긴게 하나라도 있는경우, 여기에 하나 더 담기면 짝수개라는 의미이므로 지우기
    else:
        num+=1

print(soinsulist)