백준 11653번 - 소인수분해 (PYTHON 풀이)

문제:

 

해당 문제는 입력 받은 수를 소인수분해하고 각 라인에 어떤 수로 나누었는지 출력하라는 문제이다.

 

풀이:

a=int(input())
while(a!=1):
    for i in range(2,a+1):
        if a % i == 0:
            print(i)
            a = a//i
            break

초기 코드이다. 비쥬얼스튜디오 돌렸을 땐 이상 없이 잘 되어서 제출했는데 계속 시간 초과가 나서 푸는데 오래 걸렸다..

for문 돌 때 범위가 넓어서 그런가 싶어 좀 더 줄여서 해보았는데도 해결이 안됐다.

a = int(input())

i = 2
while i * i <= a:
    while a % i == 0:
        print(i)
        a //= i
    i += 1

if a > 1:
    print(a)

어떻게 해도 해결이 잘 안되어서 서치를 통해 풀었다.

핵심 아이디어는 다음과 같다. 어떤 합성수 a가 있을 때 적어도 하나의 약수 p가 p <=루트a이다. 즉 소인수 탐색을 i*i<=a까지만 하면 루프를 조금만 돌아도 해결할 수 있게 된다.

보는 동안은 이해가 됐는데 정리하는동안 보니 또 갑자기 헷갈린다. 분명 다른 방법도 있을 것이다. 

업로드 한 뒤에 좀 더 살펴봐야겠다..!