글 읽기 - 시간 초과가 뜹니다

plse 1년 전 0

제 생각으로는 5번 줄을 처음부터 끝까지 반복해서 시간 초과가 뜬걸로 생각되는데 만약 이게 아니라면 왜 시간 초과가 뜨고 해결방법을 상세히 알려주세요

start,end=map(int,input().split())
num_list=[]
for i in range(start,end+1):
    num_list.append(i)
for eratos in range(2,end+1):
    for num in num_list:
        if eratos==num:
            continue
        elif num%eratos==0:
            b=num_list.index(num)
            num_list.pop(b)
for prime_num in num_list:
    print(prime_num)

limepencil 1년 전 0

for loop 두개가 겹처져 있는데다가 index,pop같은 O(n)함수를 사용하고 있어서 시간초과는 피하기 어려울거라 생각합니다.

힌트를 드리자면 num_list에 넣어놓고 찾는것보다 num_list=[0]*(end+1) 같은 배열로 확인하는 방법을 써보시는걸 추천합니다

plse 1년 전 0

잘 이해가 되지 않는데 다시 상세히 설명해 주실 수 있으신가요?

limepencil 1년 전 0

index같은 함수는 처음부터 리스트를 확인해서 하기때문에 for loop 하나 더 돌리는 것과 같습니다. 에라토스테네스의 체를 사용하여 end까지의 소수들을 구하고, 그중에서 start와 end사이에 있는것들만 출력하면 될것 같습니다. 에라토스네스의 체의 개념을 찾아보시기 바랍니다.

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

문제

문제

출처

ICPC

시간 초과가 뜹니다

plse 1년 전 0

limepencil 1년 전 0

plse 1년 전 0

limepencil 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말