[파이썬] 소인수분해

소인수(Prime Factor)

약수 중에서 소수인 약수

 

[예시1] 숫자 x의 약수와 소인수 찾기

# 1. 숫자 x의 약수를 divisor리스트에 저장 x = 20 divisor = [] for number in range(1, x+1):  # 1부터 x까지의 숫자를 범위로 설정   if x % number == 0:         # x를 number로 나눈 후 나머지가 0인 경우     divisor.append(number) print("{}의 약수:".format(x), divisor) divisor[0] # 2. 약수 중 소수를 찾아 pf리스트에 저장 pf = [] index = 0 for number in divisor:   # print(number)   flag = True   if number > 1:     for n in range(2, number):       if number % n == 0:         flag = False     if flag:       pf.append(number) print("{}의 소인수:".format(x), pf)

20의 약수: [1, 2, 4, 5, 10, 20] 20의 소인수: [2, 5]

 

소인수분해(Factorization in Prime Factors)

합성수를 소인수들의 곱으로 분해

 

[예시2] 숫자 x의 약수와 소인수분해 구하기

x = 72 fpf = [] n = 2 while n <= x:   if x % n == 0:     fpf.append(n)     x /= n   else:     n += 1 number = 0 print(fpf)

[2, 2, 2, 3, 3]

72의 소인수분해 값은 2^3 * 3^2

 

* a에 x를 곱하면 y의 제곱이 될 때, x에 해당하는 가장 작은 정수 구하기

 

[예시3] 수학 풀이

a = 72
72의 소인수 분해 2^3 * 3^2

→ 2^3 * 3^2 * x = y^2
→ (2^2 * 3)^2 = y^2
→ y = 12
→ 12^2 = 2^3 * 3^2 * x
→ 144 = 8 * 9 * x
→ 144 = 72 * x
→ x = 144 / 72 = 2
∴ 소인수분해 값 중 홀수 제곱을 짝수 제곱으로 만들어 주면 구할 수 있다.
→ 홀수 제곱인 소인수를 한번 더 곱하면 된다.

 

[예시4] 파이썬 풀이

a = 72 n = 2 b = [] while n <= a:   if a % n == 0:     print("소인수 : {}".format(n))     if b.count(n) == 0:   # 리스트b에 방금 구한 소인수 값이 없으면 추가       b.append(n)     elif b.count(n) == 1: # 리스트b에 방금 구한 소인수 값이 있으면 삭제       b.remove(n)         # 즉, 소인수분해 제곱값이 홀수면 b에 저장, 아니면 삭제     a /= n   else:     n += 1 print("x = ",b)

소인수 : 2 소인수 : 2 소인수 : 2 소인수 : 3 소인수 : 3 x = [2]