[BOJ] 11653 - 소인수 분해

문제

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

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

 

소인수분해 prime factorization
소수(prime)란 1과 자기 자신으로만 나누어 떨어지는 정수를 뜻하며, 인수화(factorization)란 어떤 수를 인수로 분해하는 것을 의미한다.
즉, 소인수분해는 어떤 수를 소수인 인수로 분해하는 것이다.

 

풀이

풀이 1. 2부터 N까지 모든 수에 대하여 나머지가 0인 경우 값을 출력한다.

 

코드

n = int(input())
divider = 2
while n != 1:
    if n % divider == 0:
        print(divider)
        n //= divider
    else:
        divider += 1

이 방법은 불필요한 반복이 많아 속도가 빠르지 않다.

 

풀이 2. N을 두 개 이상의 인수로 나타낼 때 인수 중 하나 이상은 반드시 √N 보다 작거나 같다는 점을 이용한다.

다만 반복문을 종료할 때, N이 1이 아닐 경우도 고려해야 한다.

 

예시)

N = 34

divider = 2, N = 17 // 2 출력

divider = 3

divider = 4

divider = 5  <<== 반복문 종료. 17도 인수이므로 출력해주어야 한다.

 

코드

n = int(input())
divider = 2
while divider * divider <= n:
    if n % divider == 0:
        print(divider)
        n //= divider
    else:
        # 1씩 증가시키는 경우 나누는 값에 짝수가 포함되므로, 홀수로만 나누도록 한다.
        divider += 2 if divider > 2 else 1 
if n > 1:
    print(n)