글 읽기 - (Python) 시간초과 문제 해결방법을 모르겠습니다 ㅠㅠ

pds8462 3년 전 0

N 보다 작은 소수를 모두 찾은 뒤, 소수로 하나씩 나눠보면서 소인수분해를 진행했습니다.

문제에선 1 <= N <= 10,000,000 이라고 명시되어 있어서

5,000,000과 10,000,000 같이 큰 수를 넣어서 돌렸을 때는 타임오버가 나오더라구요

시간을 단축 하는 방법이 뭐가 있는지 힌트라도 주시면 감사하겠습니다 ㅠ

n = int(input()) # 소인수 분해를 할 수를 입력받습니다.
PrimeNum = [] # 소수를 담을 리스트를 생성합니다.
num = [] # 소인수 분해를 한 수를 담을 리스트를 생성합니다.

if n == 1: # 만약 입력받은 값이 1이라면 아무것도 하지 않습니다.
    None
else:
    sieve = [True] * n + [True] # 에라토스테네스의 채를 이용하여 n보다 작은 소수를 구합니다.
    for i in range(2, int(n ** (1/2)) + 1):
        for j in range(i * 2, len(sieve), i):
            sieve[j] = False
    
    for i in range(2, len(sieve)):
        if sieve[i] == True:
            PrimeNum.append(i)
    
    i = 0
    while 1: # 작은 수부터 하나씩 나누어 소인수 분해를 합니다.
    	if n % PrimeNum[i] == 0:
    		num.append(PrimeNum[i])
    		n = n // PrimeNum[i]
    		
    		if n == 1:
    			break
    		continue
    	i += 1
    	
    for i in range(len(num)): # 소인수 분해 값을 한줄에 하나씩 출력합니다.
    	print(num[i])

appie701 3년 전 1

굳이 소수들을 구해서 나눠주실 필요가 없어요. 그냥 n을 for문에서 i를 2부터 n-1까지 하나씩 증가시키면서 나눠보고 나눠지면 n = n//i 하고 for문 탈출하고 다시 i = 2부터 for문을 돌리면서 n을 나누어보면

무조건 소수로만 나누어지게 됩니다. 합성수로 나눠질 경우 그 이전에 이미 소수로 나누어져야 하기 때문에 그렇습니다.

pds8462 3년 전 0

감사합니다. 문제 해결 됐습니다!!!

시간이 1300ms 나온게 아쉽긴 하지만 그래도 해결되서 기분이 좋네요 ㅎㅎ

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

(Python) 시간초과 문제 해결방법을 모르겠습니다 ㅠㅠ

pds8462 3년 전 0

appie701 3년 전 1

pds8462 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말