[기초 수학] 소인수와 소인수 분해

[ 개념 ]

• 약수(인수) 중에서 소수인 숫자를 소인수라고 한다.
• 1보다 큰 정수를 소인수의 곱으로 나타낸 것을 소인수 분해라고 한다.
  ex) 20을 소인수 분해 하면 다음과 같다. : 2^2 * 5
• 구한 소인수를 가지고 약수를 모두 구할 수 있다.

	1	5
1	1	5
2	2	10
2^2	4	20

---

실습 1 : 사용자가 입력한 수를 소인수 분해 하기

number = int(input())

n=2
while n<=number:
    if number % n == 0:
        number /= n
        print('소인수 : {}'.format(n))
    else:
        n+=1

'''
50
소인수 : 2
소인수 : 5
소인수 : 5
'''

코드 해석

n을 2부터 시작해 입력한 number에 대한 나머지 연산 값이 0 일 경우, n을 print 한다.

n을 다시 시작해 입력한 number에 대한 나머지 연산 값이 0을 만족하지 못할 경우 n을 +1 한다.

n이 number을 넘기 전에 while문을 종료한다.

---

실습 2 : 72에 x를 곱하면 y의 제곱이 된다고 한다. 

 

시행 착오

number = int(input())
num = number
n=2
a=0
ans=1
while n<=number:
    if number % n == 0:
        number /= n
        a += 1
    else:
        if a % 2 != 0:
            ans *= n
        n+=1
        a = 0
print(f'정답은 {ans} 입니다.')

리스트 없이 해보려고 다음과 같은 코드를 구상하였다.

그러나 예를 들어 12를 넣었을 때,

n이 3이 될 때 number은 1이 되어버려 while문이 종료 됐기 때문에 a값이 1일 때의 n 값을 ans에 곱할 수가 없었다.

 

리스트를 활용한 답안

number = int(input())
n=2
search_number = []
while n<=number:
    if number % n == 0:
        if search_number.count(n) == 0 :
            search_number.append(n)
        elif search_number.count(n) == 1 :
            search_number.remove(n)
        number/= n
    else:
        n+=1
print(search_number)

# 72
# [2]

코드 해석

소인수를 찾아낼 때마다 search_number에 넣고, 만약 동일한 소인수가 존재한다면 search_number에서 빼버린다.

짝이 없는 소인수만 search_number에 남기 때문에 곱했을 때 제곱이 되겠끔 하는 값의 소인수 분해 리스트를 구할 수 있다.

 

# 디버깅 하기 전

elif 가 아니라 if 라고 적어서,

가령 처음에 소인수 n이 짝이 없어 search_number에 들어갔다가

들어간 순간 search_number에 n이 하나 들어있는 셈이므로 바로 n을 빼버리는 결과를 초래하였다.

이게 도대체 무슨일..