[백준] 11653번 :소인수분해 - Python 파이썬

[백준] 11653번 :소인수분해 - Python 파이썬

 

알고리즘 분류:

• 수학
• 정수론
• 소수 판정

 

링크: https://www.acmicpc.net/problem/11653

11653번: 소인수분해

 

---

문제

정수 N이 주어졌을 때, 소인수분해하는 프로그램을 작성하시오.

입력

첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다.

출력

N의 소인수분해 결과를 한 줄에 하나씩 오름차순으로 출력한다. N이 1인 경우 아무것도 출력하지 않는다.

 

 

---

제출한 답

T = int(input())
 
#T가 1이 될때까지 인수로 나눈다
while T != 1:
  for i in range(2,int(T**0.5)+1):
    if T % i == 0:
      T = T//i
      print(i)
      break
    #나눠지는 인수가 1 이외에 없을 때 종료
    else:
      print(T)
      break

인수를 빠르게 확인하기 위해

T의 제곱근까지만 for문을 돌렸다.

T//2와 비교해 시간이 636ms에서 84ms까지 단축됐다.

 

T = int(input())
 
i = 2
while T != 1:
  if i <= T**0.5:
    if T % i == 0:
      T = T//i
      print(i)
      i = 2
    else:
      i += 1
  else:
    print(T)
    break

for문을 사용하지 않는 답. 위와 시간은 비슷하다.(76ms)

이게 최적의 답안이지만 먼가 긱한 느낌..

 

N = int(input()) 
m = 2 
while N!=1: 
    if N%m==0: 
        print(m) 
        N = N//m 
    else: 
        m += 1

제일 간편한 답.

하지만 시간이 오래걸린다.(1600ms)