[백준_python] 소인수분해 || 11653

www.acmicpc.net/problem/11653

11653번: 소인수분해

에라토스테네스의 체를 이용해야하는 줄 알았따...

#소인수분해(시간초과)

def isprime(num):
    if num == 1:
        return False
    for i in range(2, int(num**0.5)+1):
        if num % i == 0:
            return False
    return True 

n = int(input())    
prime = []
for i in range(1, n+1):
    if isprime(i):
        prime.append(i)

while n!= 1:
    for i in prime:
        if n % i ==0:
            n = n/i
            print(i)
            break

 

그래서 주어진 수의 소인수를 찾는 것이 아니라, 주어진 수까지의 모든 소수를 찾아줘버렸다
(ㅋㅋㅋㅋㅋ아무래도 답은 잘 나오지만, 주어진 수까지의 모든 소수를 찾아주는 for문으로 인해 시간초과, 필요없는 과정이였다.)

 

# 소인수분해_2

n = int(input())  
while n!=1:
    for i in range(2, n+1):
        if n % i ==0:
            print(i)
            n = n/i
            break

그래서 역시 하나씩 순서대로 값을 올려주며 나누어떨어지도록 해주었다.