백준 문제 중 11653번, 수학, ‘소인수분해’

백준 문제 중 11653번

https://www.acmicpc.net/problem/11653

문제

정수 N이 주어졌을 때, 소인수분해하는 프로그램을 작성하시오.

입력

첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다.

출력

N의 소인수분해 결과를 한 줄에 하나씩 오름차순으로 출력한다. N이 1인 경우 아무것도 출력하지 않는다.

---

풀이

소인수 분해는 결국 자연수 n 을 소수들의 곱들로 분해하여 나타 내는 것이므로 n이하의 소수들을 먼저 구해 리스트로 구한 뒤 리스트의 원소를 하나씩 꺼내 n을 소수로 나눠가며 출력 하는 식으로 코드를 구현 했다.

 # 소수인지 아닌지를 판단하는 함수 선언
def is_prime(i:int)->bool:
    
    # 1은 소수가 아니다.
    if i==1:

        return False
    
    # 2부터 비교 시작
    j=2

    # 약수의 성질을 이용해 범위 설정
    while j**2<=i:
     
        # i가 j로 나누어 떨어지면 소수가 아님
        if i%j==0:

            return False

        j+=1

    else:
 
        # 루프를 통과한 수는 소수
        return True


 # n 입력
n = int(input())

 # n이하 소수를 저장할 prime 선언
prime=[]

 # 약수의 성질을 이용해 범위 설정
for i in range(2,int(n**(0.5))+1):

    if is_prime(i):

        prime.append(i)

 # 위의 범위에 n자기자신이 포함되지 못하고 n이 소수일 경우도 있으니 예외 처리
if is_prime(n):

    prime.append(n)

 # prime의 원소들로 나누어 떨어진다면 whil 루프 시작
for p in prime:

    if n%p==0:

        # n이 p로 나누어지는 동안 p 출력
        while n%p==0:

            n//=p

            print(p)

 # 루프를 끝낸 n이 1이 아니라면 n또한 약수이므로 예외처리
if n!=1:

    print(n)

9991
97
103

배운점

내가 짠 코드가 조금 깔끔하지 않아서 다른 사람의 코드를 찾아 봤는데 성능면에서 내코드가 76ms 다른사람의 코드가 1048ms로 코드의 가독성과 성능이 약간 트레이드오프가 있는 것 같다.