[백준] 11653번 : 소인수분해 (Python)

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

 

정수 N을 소인수분해하는 문제.

import sys

input = sys.stdin.readline

# 분해
def divide(N, div):
    while(N%div==0): # 나누어떨어질 시 반복
        print(div)
        N /= div # N을 i로 나누기
        
    return N

# 소수 찾기
def prime(N):
    
    for i in range(2, N+1): 
        
        if(N%i==0): # N을 분해할 수 있는 소수이면
            N = divide(N, i) # 찾은 소수로 분해
            
        if(i >= N): # i가 현재 분해된 N보다 커지면
            break # 종료

N = int(input()) # 숫자 N
primes = prime(N) # N의 소수

 

 

 

[문제풀이]

---

 

일반적으로 소인수분해란 더 이상 나누어질 수 없는 작은 수로 분해한다는 뜻이다.

 

 

 

여기서 분해되는 2와 3은 소수다.

즉, 소인수분해로 나누어지는 모든 수는 1과 자기 자신 외에는 분해될 수 없는 수, 소수다.

 

그럼 소인수 분해를 하려면 일단 소수를 구하고, 그 소수 중 N을 분해할 수 있는 수를 찾아 분해해야 하는데....

파이썬은 느려서, 시간 초과가 난다.

 

그래서 밑의 블로그를 참조, 소수를 구하는 과정과 소인수 분해를 하는 과정을 섞었다.

소수를 찾을 때 N이 그 소수로 나누어 떨어진다면 바로 N을 분해하는 방식으로!

 

 

 

참고 : https://blog.naver.com/pcw3261/223439020084