[백준] 11653번 소인수분해

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

문제

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

풀이

첫번째 도전 : 시간초과

n의 소수를 구하고 그 소수 중 나누어 떨어지는 걸 찾음

import math, sys
input = sys.stdin.readline

n = int(input())

def prime_num(x):
    for i in range(2, int(math.sqrt(x))+1):
        if x%i == 0:
            return False
    return x

array = []

for i in range(2, n+1):
    x = prime_num(i)
    if x != False:
        array.append(x)

answer = []

while n!=1:
    for i in array:
        if n%i==0:
            answer.append(i)
            n //= i
            continue
answer.sort()
for i in answer:
    print(i)

두번째 도전 : 시간 너무 오래 걸림

import sys
input = sys.stdin.readline

n = int(input())

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

세번째 도전 : 남이 쓴 코드 외워버림

n = int(input())

for i in range(2, int(n**0.5)+1):
    while n%i == 0:
        print(i)
        n //= i

if n>1:
    print(n)