Math07소인수분해(11653)

문제

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

입력

첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다.

출력

N의 소인수분해 결과를 한 줄에 하나씩 오름차순으로 출력한다. N이 1인 경우 아무것도 출력하지 않는다.

풀이

• for문 돌면서 각각을 while로 확인 > 이게 제일 시간 효율 좋다

코드

import sys
sys.stdin = open("input.txt","rt")

def input():
    return sys.stdin.readline().rstrip()


N = int(input())
tmp = N


for i in range(2,N+1):
    if tmp == 1:
        break
    while tmp % i== 0 :
        tmp //= i
        print(i)

배운 것

1. 시간초과

import sys

def input():
    return sys.stdin.readline().rstrip()


N = int(input())
tmp = N
arr = [0]*(N+1)
prime = []
cnt = 0 
if N == 1:
    exit()

for i in range(2, N+1):
    if arr[i] == 0:
        prime.append(i)
        for j in range(i, N+1, i):
            arr[j] = 1


while(True):


    if tmp % prime[cnt] == 0:
        print(prime[cnt])
        tmp = tmp / prime[cnt]
        
    else:
        cnt = cnt + 1
        if cnt == len(prime):
            break

2. 시간초과

import sys

def input():
    return sys.stdin.readline().rstrip()


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

3. 맞음

import sys

def input():
    return sys.stdin.readline().rstrip()


N = int(input())
tmp = N
while(True):
    if tmp == 1:
        break;    
    for i in range(2,N+1):
        if tmp % i == 0:
            print(i)
            tmp = tmp / i
            break

코멘트