[Baekjoon] 11653. 소인수분해 [S5]
📚 문제
https://www.acmicpc.net/problem/11653
소수를 구하거나 소인수 분해를 구할 땐 제곱근을 생각하는 것이 매우 중요하다.
소인수 분해에서는 구할 정수의 제곱근 이상의 값이 하나 나오거나 안 나온다.
📒 코드
N = int(input())
mok = N
for i in range(2, N+1): # 소인수는 2부터 나누며 구한다.
if i * i > N: # 소인수가 수의 제곱근보다 큰 경우는 한가지 밖에 안나온다.
# 하나만 나오거나 없으니까 1이거나 현재 mok이 나머지 소인수가 된다.
break
while mok % i == 0: # 나누어 떨어지면 소인수니 출력한다.
mok //= i # 나누어서 수를 줄인다.
print(i)
if mok != 1:
print(mok)
🔍 결과
Author And Source
이 문제에 관하여([Baekjoon] 11653. 소인수분해 [S5]), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@yunhlim/Baekjoon-11653.-소인수분해-S5저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)