글 읽기 - 파이썬 시간초과

yeslee5004 3년 전 0

에라토스테네스의 체를 이용해서 풀었는데 어떤 코드에서 시간이 초과되는건지 잘 모르겠습니다.

import math

sieve = []
M, N = map(int, input().split())

for i in range(M, N + 1):
    sieve.append(i)

if 1 in sieve:
    sieve.remove(1)
else:
    for j in range(2, math.ceil(math.sqrt(sieve[-1]))):
        for k in sieve:
                if k / j == 1:
                    pass
                elif k % j == 0:
                    sieve.remove(k)

for answer in sieve:
    print(answer)

dietomorrow 3년 전 0

별개로 else문을 쓰신 이유는 무엇인가요?

sieve.remove(k)는 shift연산이 일어나서 O(N)의 시간이 걸리는 작업입니다.

yeslee5004 3년 전 0

그러네요;

그래서 밑 부분을 이렇게 수정했는데도 같은 시간 초과가 나옵니다.

elif j < k:
    if k % j == 0:
        sieve.remove(k)

dietomorrow 3년 전 1

remove에 O(N)의 시간이 소요되어 똑같습니다.

보통 에라토스테네스의 체를 사용할 때 수의 범위의 bool 배열을 만들어서 소수가 아니면 False로 만들어주고 True인 경우 출력해주는 식으로 사용합니다.

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

문제

문제

출처

ICPC

파이썬 시간초과

yeslee5004 3년 전 0

dietomorrow 3년 전 0

yeslee5004 3년 전 0

dietomorrow 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말