글 읽기 - 에라토스테네스의 체를 쓰면 왜 시간초과가 날까요??

qwer9412 3년 전 0

에라토스테네스의 체로 소수를 모두 구하는데 1초가 안걸리고 10000000이하 소수는 400여개여서 시간초과가 안날줄 알았는데 시간초과가 나네요 ㅠㅠ

혹시 왜 그런지 설명해 주실분 계실까요..?

import sys

primes = []
def mapPrime():
    primeVisit = [False] * 10000001
    for i in range(2, int(10000000 ** 0.5)):
        if not primeVisit[i]:
            primes.append(i)
        for j in range(i, int(10000000 ** 0.5), i):
            primeVisit[j] = True

mapPrime()
n = int(sys.stdin.readline())
while n > 1:
    for i in primes:
        if n % i == 0:
            print(i)
            n = n // i
            break

rlarla97 3년 전 1

1. 10,000,000 이하의 소수가 전부 들어가 있는 코드가 아닙니다. 또한 소수 구하는 방법 자체도 primeVisit의 flag에 따라 for - j 를 반복여부를 정할 수 있는데, 그렇지 않고 모두 for문을 돌려버리니 mapPrime()에서 시간초과가 나버립니다.

2. primeVisit으로 소수를 구하신 것을 다시 primes 리스트에 모두 넣고 다시 빼내기 때문에 그만큼의 오버헤드가 더 발생합니다.

3. 반복문 출력부분에서도 리스트를 반복적으로 로드하여 요소를 빼냅니다. 이또한 불필요한 오버헤드 비용이 큽니다.

qwer9412 3년 전 0

두 분 모두 답변 감사합니다!

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

문제

문제

출처

ICPC

에라토스테네스의 체를 쓰면 왜 시간초과가 날까요??

qwer9412 3년 전 0

rlarla97 3년 전 1

qwer9412 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말