소인수분해.python

문제 설명

소인수분해란 어떤 수를 소수들의 곱으로 표현하는 것입니다. 예를 들어 12를 소인수 분해하면 2 2 3 으로 나타낼 수 있습니다. 따라서 12의 소인수는 2와 3입니다. 자연수 n이 매개변수로 주어질 때 n의 소인수를 오름차순으로 담은 배열을 return하도록 solution 함수를 완성해주세요.

제한사항
2 ≤ n ≤ 10,000
입출력 예

n	result
12	[2, 3]
17	[17]
420	[2, 3, 5, 7]

풀이

# 나의 풀이
def solution(n)
	i = 2
    answer = []
    # i제곱이 n 보다 작을때
    while i * i <= n :
        if n % i == 0 :
            answer.append(i)
            n //= i 
        	# 인수를 구하는 과정이니까 +1 을 해주면 안된다.
            # +1 을 해주면 2가 몇번 들어가는지 확인 할 수 없다.
        else :
            i += 1
    if n > 1 :
        answer.append(n)
    a = set(answer)
    b = list(a)
    b.sort()
    return b
    
# 좋은 풀이 
def solution(n):
    i = 2 
    answer = []
    # n 을 줄여줄 거기에 작은동안만 실행 ( 굳이 제곱할 필요 없음 )
    while i <= n :
        if n % i == 0 :
            # 소인수를 구하기 위한 과정 인수가 이미 있으면 추가 x
            if i not in answer :
                answer.append(i)
            n /= i
            
        else : 
            i += 1
    
    return answer