[백준/Python] 11653번 - 소인수분해

 

문제

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

 

정수 N이 주어졌을 때, 소인수 분해를 해야한다.

(단, 1 입력 시 출력X)

 

 

풀이

 

 

 

정수 N을 소인수분해 하기 위해서, 정수 N이 소수인지 아닌지 판별하는 방법을 활용했다.

 

정수 판별방법

 

정수 N의 제곱근을 a라고 했을 때, 정수 N의 소인수 중 a보다 크거나 같은 소인수가 존재 하면, 나머지 소인수는 전부 a보다 작거나 같을 수 밖에 없다.

그러므로 for 문을 이용해 2부터 N의 제곱근 사이의 수로 정수 N이 나눠지는지 확인하고, 나눠지고 남은 수를 출력하면 소인수 분해가 끝난다.

​

1. N의 소인수들이 전부 a보다 작거나 같을 경우 정수 N의 소인수를 전부 구할 수 있다.
2. N의 소인수 중 a보다 큰 소인수가 있을 경우 가장 큰 소인수를 제외한 나머지 소인수들은 a보다 작을 수 밖에 없으므로 2~a 사이의 소수들을 구하고, 남은 소수를 구하면 정수 N의 소인수를 전부 구할 수 있다.
3. N이 소수라면 N이 그대로 출력 된다.

 

Code

 

N= int(input())
a=int(N**0.5+1)
if N==1:
    pass
else :
    for i in range(2, a):
        while True:
            if N%i:
                break
            else :
                N /= i
                print(i)
    if N>1:
        print(int(N))

 

(i의 범위를 소수로 설정하지 않고 그냥 2~a로 설정한 이유는 i가 4, 6 과 같이 소수가 아닐 경우 이미 앞에서 i가 소수인 2, 3일 때 나눴기 때문에 break문을 통해 빠져나가기 때문이다.)

---

 

 

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