[백준] 11653번: 소인수 분해 / 파이썬

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

11653번: 소인수분해

 

소인수 분해란?

자연수를 소수들만의 곱으로 나타내는 것을 소인수 분해라고 한다.

1보다 큰 자연수는 유한개의 소수(소인수)의 곱의 꼴로 나타낼 수 있는데, 이 곱의 꼴을 자연수의 소인수 분해라고 한다.

 

예) 24의 소인수 분해

24 = 2 x 2 x 2 x 3 = 2^3 x 3

 

N = 24 일 때의 소인수 분해를 통해 알고리즘을 알아보자.

 

d = 2 (2부터 나누어떨어지는지 확인한다.)

24는 2로 나누어떨어지므로 소인수에 2를 담고, 24는 2로 나눈 12가 된다.

N = 12

소인수 = 2

 

12는 2로 나누어떨어지므로 소인수에 2를 담고, 12는 2로 나눈 6이 된다.

N = 6

소인수 = 2, 2 

 

6은 2로 나누어떨어지므로 소인수에 2를 담고, 6은 2로 나눈 3이 된다.

N = 3

소인수 = 2, 2, 2

 

3은 2로 나누어떨어지지 않으므로, 2를 그 다음 수인 3으로 증가시킨다.

 

d = 3

3은 3으로 나누어떨어지므로 소인수에 3을 담고, 3은 3으로 나눈 1이 된다.

N = 1

소인수 = 2, 2, 2, 3

 

N이 1이 되면 소인수 분해를 종료한다.

 

 

코드

N = int(input())  # 나누어지는 수
d = 2  # 나누는 수

while N != 1:
    if N % d != 0:
        d += 1
    else:
        N //= d
        print(d)

실행 결과

# 입력
20

# 출력
2
2
5

 

하지만 이 코드는 N이 커질수록 비효율적이다.

 

 

---

• 1 x 16 = 16
• 2 x 8 = 16
• 4 x 4 = 16
• 8 x 2 = 16
• 16 x 1 = 16

2 x 8 = 16 은 8 x 2 = 16 과 대칭이다. 즉, 가운데 약수를 기준으로 해서 각 등식이 대칭적인 형태를 보이기 때문에 우리는 특정한 자연수 N이 소수인지 확인하기 위해 바로 가운데 약수까지만 '나누어떨어지는지' 확인하면 된다.

위의 예시에서는 가운데 약수가 4이기때문에 2부터 4까지만 확인하면 된다. 다시 말해 제곱근(가운데 약수)까지만 확인하면 된다.

 

참고

2021.07.28 - [자료구조 알고리즘] - [알고리즘] 소수의 판별 / 약수 / 에라토스테네스의 체 / 파이썬

[알고리즘] 소수의 판별 / 약수 / 에라토스테네스의 체 / 파이썬

 

개선된 코드

import math

N = int(input())    # 나누어지는 수
d = 2               # 나누는 수
sqrt = int(math.sqrt(N)) # 나누어지는 수의 제곱근

# 나누는 수가 제곱근이하인 동안
while d <= sqrt:
    if N % d != 0:  # 나누어 떨어지지 않으면
        d += 1      # 나누는 수 1 증가
    else:           # 나누어 떨어지면
        print(d)    # 소인수니까 출력하고
        N //= d     # 나누어지는 수도 갱신

# 제곱근까지 나누어떨어지지 않으면, 소수이므로 그대로 출력
if N > 1:
    print(N)

실행 결과

# 입력1
17

# 출력1
17

# 입력2
12

# 출력2
2
2
3