[백준] 11653 파이썬 (소인수분해)

5798 단어 백준백준

나의 시간 초과 코드

  • 코드
n = int(input())
list = []

#n보다 작은 소수들을 리스트에 넣기
for i in range(2, n+1):
    for j in range(2,int(i**0.5)+1):
        if i%j==0:
            break
    else:
        list.append(i)

#n이 소수로 나눠지면 나누기 (n이 1이 될 때까지 반복)
while n!=1:
    for i in list:
        if n%i == 0:
            n = n/i
            print(i)
            break

  • 풀이
    나는 n을 입력 받고
    n보다 작은 소수들을 구해서 list에 담았다.

    for j in range(2,int(i**0.5)+1):
            if i%j==0:
                break
        else:
            list.append(i)

    안에 있는 for문의 range가 2부터 int(i**0.5)+1 인 이유는
    어떤 자연수에 약수의 개수는 제곱근을 기준으로 대칭이기 때문이다.
    예를 들면, 12의 약수는 1,2,3,4,6,12 (6개)인데
    루트12(=3.xx)보다 박은 수가 3개이고, 큰 수가 3개이다.

    그 다음 n이 1이 될 때까지 소수로 나누었다.
    그런데 이런식으로 했더니 시간 초과가 떴다,,,,;;;



정답 코드

  • 코드
n = int(input())
i = 2
while n!=1:
    if n%i == 0:
        print(i)
        n = n/i
    else:
        i+=1

  • 풀이
    굳이 소수를 구해서 나누지 말고
    '나눠지는 가장 작은 수'를 구하면 된다.

좋은 웹페이지 즐겨찾기