[백준/python] 11653 소인수분해

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

11653번: 소인수분해

 

• 사용언어 : python
• 알고리즘 : 수학, 정수론, 소수판정
• Solved.ac Tier : Bronze I

 

 

python 코드

1. 문제 정리

간단하게 에라스토테네스의 체 알고리즘을 활용하여 풀면 되는 문제이다. 소수 찾기 알고리즘을 사용하면 간단하게 해결할 수 있는 문제이다. 

나는 soinsoo라는 함수를 재귀를 활용하여 해결 하였다.

def soinsoo(k):
    for i in range(2, k):
        if k % i == 0:
            ans.append(i)
            soinsoo(int(k / i))
            return

2부터 k까지의 수를 모두 나누어 보아 떨어지는 수가 존재하면 그 값을 ans 배열에 삽입하고 다시 soinsoo 함수를 돌 수 있도록 만들어 주었다.

 

2. 완성 코드

n = int(input())
ans = list()
if(n == 1): exit(0)
def soinsoo(k):
    for i in range(2, k):
        if k % i == 0:
            ans.append(i)
            soinsoo(int(k / i))
            return
    ans.append(k)

soinsoo(n)
ans.sort()
for i in ans:
    print(i)