글 읽기 - python3 에라토스테네스체 사용했는데.. 시간초과 질문드립니다.

chsun0303 6년 전 0

시간초과가 나서 질문한 내역들을 쭉 보다가

에라토스테네스체를 사용해 보라는 다른 댓글들을 봤습니다.

그런데도 시간초과가 나는데 어떻게 해야할지 궁금합니다.

감사합니다.

import sys

n = list(map(int, sys.stdin.readline().strip().split(" ")))

result = []
candidate = [i for i in range(n[0], n[1])]
base = 2
product = base

while candidate:
    while product < n[1]:
        if product in candidate:
            candidate.remove(product)
        product += base

    if base >= n[0]:
        result.append(base)
    base = candidate[0]
    product = base
    del candidate[0]
result.append(base)

for i in range(len(result)):
    print(result[i])

djm03178 6년 전 0

파이썬에서 list를 내부적으로 배열로 관리하기 때문에 원소를 제거하는 연산은 뒤의 원소들을 하나씩 다 끌어오는 O(n) 시간이 걸린다고 알고 있습니다. 특히 0번째 원소를 제거하는 것은 전체 원소의 수만큼의 시간을 고스란히 소비할 것 같네요.

에라토스테네스의 체는 플래그를 통해서 관리하면 효율적으로 만들 수 있습니다.

djm03178 6년 전 1

참고로, M 이상 N 이하의 소수를 구해야 하는데 이 코드는 M 이상 N 미만의 소수를 구하고 있습니다.

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

문제

문제

출처

ICPC

python3 에라토스테네스체 사용했는데.. 시간초과 질문드립니다.

chsun0303 6년 전 0

djm03178 6년 전 0

djm03178 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말