[백준] #11653.소인수분해

#11653. 소인수분해

문제 설명:

N을 소인수분해하는 문제 

 

 

오답노트:

문제 풀이과정에서 범위가 N까지의 소수 리스트를 만들어 첫 시도는 시간초과되었으며 

두 번째도 간단한 코드를 구현하였으나 채첨시간이 매우 오래걸렸다. 

- 두 번째 시도:성공하였으나 시간이 오래 걸림(1156ms)

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

- 최종코드(다른 코드 참조, 40ms)

N = int(input())
for i in range(2, int(N**0.5)+1):
    while N % i == 0:
        print(i)
        N //= i

if N > 1:
    print(N)

: 시간을 단축하기 위해서 소인수분해하는데 있어, 어떤 수 N을 나누는 수는 제곱근 이상으로 값이 필요하지 않기 때문에 반복문을 제곱근까지로 지정함으로써 반복횟수를 감축시킨다. 

하지만 이전 코드랑 비교하면 3과 5와 같은 자신의 print함수는 자신의 범위까지 반복문이 진행되지 않기 때문에 

N > 1일 때의 경우를 가정하여 자기 자신을 프린트하는 코드를 추가해 주어야함. 

- 추가적인 코드(1120ms)

N = int(input())

for i in range(2,N+1):
    if N == 1: break
    while(N % i == 0):
        N = N // i
        print(i)

: 시간을 단축시키고자 소인수분해가 완료되면 break되는 코드를 작성하였으나

소인수가 없는 큰 수 같은 경우, 반복문을 다 돌기 때문에 시간 절약에 있어서 처음 코드랑 별반 차이가 없다.