[백준] 11653 파이썬 (소인수분해)
나의 시간 초과 코드
- 코드
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
- 풀이
굳이 소수를 구해서 나누지 말고
'나눠지는 가장 작은 수'를 구하면 된다.
Author And Source
이 문제에 관하여([백준] 11653 파이썬 (소인수분해)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@0sunset0/백준-11653-파이썬-소인수분해저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)