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

http://acmicpc.net/problem/11653

{코드}

n = int(input())
for i in range(2, n):
	if i*i > n:
		break
	while n%i == 0:
		print(i)
		n //= i
if n > 1:
    print(n)

{설명}

이 문제의 요점은 while문 안으로 들어가는 i가 무조건 소수라는 것이다.

그 이유는 어떤 수 n은 어떤 소수로 나누어지지 않을때까지 나누면 그 소수의 배수들로는 나누어지지 않기 때문이다.

(예: n = 2^7 * 3^2 * 7*8이면 2로 나누면 2의 배수가 아니게 된다)

그리고 n의 약수는 루트n까지만 확인하면 되기 때문에 i*i가 n보다 크면 반복문을 나온다. 

반복문을 마친 n이 1보다 크면 n이 소수이기 때문에 출력한다.

(6일때 i가 2로 나누면 n이 3이 되고 반복문을 나온다 / 8이면 n이 1이 되어 나오기 때문에 출력하지 않는다)