글 읽기 - 시간초과(python과 pypy)

kisin1530 3년 전 0

파이썬으로 제출하면 시간초과가 뜨지만 pypy로 제출하니 시간초과가 되지 않았습니다.

검색을 해봐도 제 머리로는 도저히 이해가 되지 않아서 질문드립니다.

import sys

def erasto():  # 아리스토텔래스의 채 (미리 완성 > 시간단축)
    Prime_list = [True] * 10000
    for i in range(2, 101):
        if i:
            for j in range(i*i, 10000, i):
                Prime_list[j] = False
    return Prime_list

def check_Goldbach(n):
    Primes = erasto()
    for i in range(n//2, n, 1):  # 중앙 가장 큰 값부터 확인
        if Primes[n-i] and Primes[i]:
            return print(n-i, i)

t = int(sys.stdin.readline().rstrip())

for i in range(t):
    n = int(sys.stdin.readline().rstrip())
    check_Goldbach(n)

knight2995 3년 전 1

골브바흐의 파티션을 구하는 check_Goldbach() 함수안에서 계속해서 erasto() 함수를 호출하기 때문에 생기는 문제로 보입니다.

kisin1530 3년 전 0

감사합니다! 덕분에 해결했습니다!

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

문제

문제

출처

ICPC

시간초과(python과 pypy)

kisin1530 3년 전 0

knight2995 3년 전 1

kisin1530 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말