글 읽기 - 시간을 어떻게 해야 줄일 수 있을까요

snowscale 5년 전 0

PyPy3로 돌려도 시간 초과가 뜹니다.

에라토스테네스의 체가 시간을 제일 잡아먹지 않을까 싶었지만 이건 ms 직접 측정해보면 300대로 준수하게 나오는데, 어디서 타임 로스가 일어나고 있는지 모르겠습니다.

입출력에서 발생하고 있는 걸까요?

import sys


eratos = [False if i % 2 == 0 else True for i in range(1000001)]

eratos[1] = False
eratos[2] = True

for i in range(3, len(eratos), 2):
    if not eratos[i]:
        continue
    for j in range(i*i, len(eratos), i*2):
        eratos[j] = False

result = ''

while True:
    num = int(sys.stdin.readline())

    if num == 0:
        break
    else:
        a = b = 0

        for i in range(3, num//2+1, 2):
            c, d = i, num - i
            if not (eratos[c] and eratos[d]):
                continue

            if d-c >= b-a:
                a, b = c, d

        if a == b == 0:
            result = "Goldbach's conjecture is wrong."
            break

        else:
            result += '%d = %d + %d\n'%(num, a, b)

sys.stdout.write(result)

njw1204 5년 전 0

왜 result 변수에 담아놓고 한번에 출력하나요? 괜히 수백만바이트짜리 문자열 연산만 해서 시간 초과를 유발합니다. 그냥 그때그때 출력하면 됩니다. 그리고 100만 길이의 배열에 소수의 참거짓유무를 저장하는 것보단 소수만 따로 빼서 저장하고 그걸 활용하는게 좋습니다.

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

문제

문제

출처

ICPC

시간을 어떻게 해야 줄일 수 있을까요

snowscale 5년 전 0

njw1204 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말