[PS][BOJ/11054]-소인수 분해

문제 설명

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

입력

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

출력

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

문제 분석 과정

우선 최선의 풀이가 아니라는건.. 장담한다.. 시간복잡도나 공간복잡도 그리고 접근방법도도 옳바르지 않을 지도 모른다,, 하지만, 우선 접근방법은 다음과 같다.

문제의 요구 사항은 나눈 것들을 모아 오름차순으로 출력하는 것이다.해서 반복문을 사용해야하는데,
언제끝날지 갯수가 정해져 있지않다. 이럴땐 while문을 사용해야한다.

  반복할 횟수를 알고 있을땐  for 문 
  반복할 횟수를 모를땐  while 문 

그 다음은 어떤 것을 나누어주어야할지 선택해줘야한다, 소수들 중에서 선택해주는게 정답이겠지만, for 문으로 2부터 탐색해도 상관은 없다.(당연히 시간복잡도는 커진다.) 왜 상관이 없냐면, 2 ,3, 4,, 이렇게 나아갈때, 만약 4로 나누어야한다면 어차피 2를 지나가기 때문에 2를 두 번 나누어 저장한다. 따라서 어차피 소수로 어팬드되게 된다.
해서 for 문으로 나눌 녀석을 탐색해주고 n을 그 친구(i)로 나누었을 때, 나머지가 0이라면?
결과 리스트에 추가해준다. i로 나누었으니 n을 i로나눈 몫을 초기화해준다. 이 for 문은 나눌 녀석을 찾는 for 문이였으므로 더 이상 반복될 필요가 없다. 따라서 break.

정리하면.
while 반복문으로 n이 1이 될때 까지 진행해주고,
for 반복문으로 n을 나눌 i를 찾아준 후 찾으면 결과리스트에 추가,
모든 반복문이 끝난 후 정렬(아마 안해도될것이다.. 혹시 모르니 ,,그냥 해 ) 하고 출력하면 정답이 된다.

소스코드

n = int(input())
arr = []
while n != 1:
    for i in range(2,n+1):
        if n%i == 0:
            arr.append(i)
            n = n//i
            break

arr.sort()
for i in range(len(arr)):
    print(arr[i])

분류

수학(math), 정수론(number_theory), 소수 판정(primality_test)

문제 원본
소스코드 원본