Week2-6 | prime_factorization.py

Week2-6. Prime factorization(소인수분해)

• Prime number(소수) : 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수이다.

• Prime factorization(소인수분해): 1보다 큰 자연수를 소수들만의 곱으로 나타내는 것이다.

 #예제1: 100-1000사이의 난수를 소인수 분해하고 각각의 소인수에 대한 지수를 출력하는 프로그램 코드

 import random

 randNum = random.randint(100,1000)
 primeDiv = []
 n = 2

 print('Random number : {}'.format(randNum))

 num = randNum  #randNum을 유지하면서 반복문을 실행하기 위해 한번 더 다른 변수에 할당한다.

 while n <= num:
     if num % n == 0:
         primeDiv.append(n)
         num /= n   

     else:
         n += 1

 print('Prime factorization of {} : {}'.format(randNum,primeDiv))

 print('-'*10)

 tempNum = 0

 for n in primeDiv:  #list with 'for' : list의 요소값이 순서대로 n에 할당된다.
     if tempNum != n:
         print('Exponential of {} : {}'.format(n,primeDiv.count(n)))  #list.coount(n):list에 특정 요솟값이 몇개 있는지 출력한다.
         tempNum = n

#예제2: 72에 x를 곱하면 y의 제곱이 된다고 할 때, 가장 작은 정수 x를 구하는 코드

 n = 2
 num = 72
 primeDivisor = []

 while n <= num:

     if num % n == 0:
         if primeDivisor.count(n) == 0:
             primeDivisor.append(n)
         elif primeDivisor.count(n) == 1: #이미 같은 소인수가 입력되어 있는 경우 해당 소인수를 지운다.
             primeDivisor.remove(n)

         num /= n                         # 나눈 몫을 userNum에 할당한 후 소인수 분해를 이어간다.

     else:
         n += 1

 print('x = {}'.format(primeDivisor))     #1번 곱해진 소수만 남는다.