소인수분해.. 어떻게 해?

python으로 소인수 분해를 하려고 했는데 세상에..

어떻게 계산해야 할지 모르겠다. 

 

주어진 값을 x 라고 했을 때

x를 1이 아닌 가장 작은 소수(2)부터 나누어지지 않을 때까지 나누어야 하고, 

그 다음 소수(3, 5, 7, 11..) 주어진 값이 1이 될 때까지 나누어야 한다.

 

내가 짠 알고리즘은 이렇다.

x = 440
count = 2
answer = []

while x != 1:
    if n % count != 0:
        count += 1
    elif n == 1:
        break
    else:
        answer.append(count)
        n = int(n / count)
  
    print(n, count)
print(sorted(list(set(answer))))

count = 2

>> count가 소수가 될 값이다. 

>> 1이 아닌 가장 작은 소수 2로 처음 count를 설정한다. 

 

answer = []

>> 소인수를 담을 리스트

 

 

while문을 사용한다.

>> x가 1이 될 때까지 아래 메소드를 반복해서 돌려야 하기 때문이다.

 

메소드 분석

if n%count != 0:

   count += 1

>> n을 count로 나눈 나머지가 0이 아니면 

>> = count가 n의 소인수면

>> ex) 440 을 2로 나누면 나머지가 0이므로 소인수가 될 수 있다.

>> ex) 440 을 3으로 나누면 나머지가 2이므로 소인수가 될 수 없다.

>> ex) 440 을 4로 나눌 수 는 없다. 2로 이미 나누어졌을 것, 4는 소수가 아니다.

 

elif n == 1:

   break

>> n이 1이라는 것은 소수로 모두 나누어졌다는 의미이다. 

>> while문을 빠져나가도록 break

 

else:

   answer.append(count)

   n = int(n/count)

>> n을 count로 나눴을 때 0이고, n이 1이 아닌 경우(AND 조건)

>> 소인수 리스트에 append 메소드를 사용하여 현재 count 값 추가

>> n은 현재 소인수로 나눈 값으로 교체한다. 

 

---

코드를 돌리면 이런 루트로 값이 출력될 것

count = 2, answer = [], n = 440, n/count = 220

count = 2, answer = [2], n = 220, n/count = 110

count = 2, answer = [2,2], n = 110, n/count = 55

count = 3, answer = [2,2,2] n = 55,

count = 4, answer = [2,2,2] n = 55,

count = 5, answer = [2,2,2] n = 55, n/count = 11

count = 6, answer = [2,2,2,5] n = 11

count = 7 ... count = 11, answer = [2,2,2,5] n = 11, n/count = 1

count = 12, answer = [2,2,2,5,11] n = 1

break (n = 1 이므로)

---

print(sorted(list(set(answer))))

>> answer = [2,2,2,5,11]

>> set() 메소드 : 중복 제거  [2,5,11]

>> sorted() 메소드 : 정렬  [2,5,11]

 

440 소인수분해 결과 [2,5,11] 로 출력된다.