[백준 알고리즘] 11653번 소인수분해 _ 파이썬 python

www.acmicpc.net/problem/11653

11653번: 소인수분해

 

 

 

소인수분해는 결국 2부터 차례대로 돌릴 수밖에 없는데요.

 

여기서 핵심은 앞에 숫자에서 나눌 수 있을 만큼 나눈 다음에 다음 숫자로 넘어가야 합니다.

 

 

그래서 while을 사용하여 나눠질 때까지 계속 나누고 난 뒤 for문을 통해서 다음 숫자로 가는 방법으로 코드를 짰습니다.

 

n = int(input())

if n == 1:
    print('')

# 2부터 하나씩 나눠보기
for i in range(2, n+1):
    if n % i == 0:
    	#해당 숫자로 나눌 수 없을 때까지 나누기
        while n % i == 0:
            print(i)
            n = n / i

 

여기서 if는 숫자가 나눠질 수 있는지 판별하는 역할을 합니다.

if 없이 while로만 해도 코드는 잘 돌아가지만 if가 있으면 코드가 빨리 돌아갑니다.

 

 

 

아래 첫번째는 if 없이 두 번째는 if를 넣고 돌려봤는데요.

 

보시다시피 if가 있는 게 시간이 약간 더 빠릅니다.