#16. Algorithm12_python) 소인수 분해

문제) 소인수 분해

정수를 입력받아, 소인수를 구해 출력하시오

 

* 전략

• n 이하의 소수를 리스트 형태로 리턴하는 메서드를 만든다.
  • 이 메서드를 위해서 특정 수가 소수인지 판단하는 메서드를 먼저 만든다.
• n 이하의 소수 중 n을 나눴을 때, 떨어지는 소수들을 리스트 형태로 출력하는 메서드를 만든다.

---

 

step1) 소수 판별 메서드      #12. Algorithm08) 소수 판별 참조

  # 소수 판별
  def isPrime(n):
      answer = True
      for i in range(2, n):
          if n % i == 0 :
              answer = False
              break
      return answer
  
  print(isPrime(8))
  >>>
  Flase

 

step2) n 이하 소수 찾기 : 일반 

n = 30
primes = []

for i in range(2, n+1):
    if isPrime(i):
        primes.append(i)
        
print(primes)

>>>
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

 

step3) n 이하 소수 찾기 : 메서드

 # 소수 찾기 메서드
 
  def findPrimes(n):
      primes = []
      for i in range(2, n+1): 
          if isPrime(i):
              primes.append(i)
      return primes
  
print(findPrimes(12))

>>>
[2, 3, 5, 7, 11]

 

step3) 소인수 분해 메서드

def algo12(n):
    factors = []               # 소인수 담을 리스트 생성
    primes = findPrimes(n)     # n의 소수 리스트를 추출
    for i in primes:
        while (n % i == 0):    # 소수 중 나누어 떨어지는 수(약수)를 찾는다
            factors.append(i)  # 리스트에 추가
            n = n // i
    return factors

n = int(input('숫자 입력 : '))
print(f'{n} 소인수 분해 : {algo12(n)}')

>>>
숫자 입력 : 48
48 소인수 분해 : [2, 2, 2, 2, 3]

---

# 배운 점

• 로직이 복잡해지니, 하나의 알고리즘으로 해결하기 힘듦
• 따라서 문제 해결을 위한 사전 메서드를 만들어야 함
• 이렇게 스텝을 밟아가는 과정을 잘 익히고, 기획하는 능력을 키워야 할 듯

# 소회

• 구글링 결과, 더 효율적인 해결 방법들이 많음
• 값이 작은 수를 판별할 때는, 효율성이 문제가 되지 않지만 숫자가 커지면 속도 차이가 엄청남
• 지금부터도 이 같은 관점으로 고민을 하고, 실력이 더 쌓이면 본격적으로 구현해보기