글 읽기 - 시간초과가 발생합니다(파이썬)

alftjd1 4년 전 0

시간 초과 문제가 발생하는데 해결방법을 여쭙고 싶습니다.

(참고 : 입력케이스는 6<=n<=1000000 이므로 1~5는 정상적으로 작동하지 않습니다.)

import sys
def Sieve_of_Eratosthenes(number_bool):
    i = 1
    while True:
        i += 1
        if number_bool[i]:
            for j in range(2,divmod(n,i)[0]+1):
                number_bool[i*j] = False
        if i ** i > n:
            number_bool[2] = False
            return number_bool

def result():
    i = 0
    for i in range(n):
        i += 1
        if number_bool[i]:
            if number_bool[n-i]:
                if n-i > i:
                    return print('{} = {} + {}'.format(n,i,n-i))
                return print('{} = {} + {}'.format(n,n-i,i))
    return print('''"Goldbach's conjecture is wrong."''')

while True:
    n = int(sys.stdin.readline())
    if n != 0:
        number_bool = [False,False] + [True] * (n-1)
        Sieve_of_Eratosthenes(number_bool)
        result()
        continue
    break

1207koo 4년 전 1

Sieve_of_Eratosthenes를 여러 번 실행할 이유가 없습니다.

n<=1000000이라면 Sieve_of_Eratosthenes(1000000짜리) 를 한 번만 실행해도 되지 않을까요?

어차피 배열 값이 n에 따라 달라지는 것도 아니니깐요(n에 따라 길이가 달라지긴 하지만 어차피 n이 작을 때는 부분 배열이 되므로 상관 없습니다)

그리고 n=4가 안 들어옵니다

그러므로 홀수 소수만 체크하면 되므로(2+2=4가 소수2가 쓰이는 유일한 해) i+=1부분을 i+=2(물론 홀수만 돌 수 있도록 해야 하는데 예외 처리를 좀 해줘야 할 수 있습니다.)

등으로 바꿔서 더 빠르게 할 수도 있습니다.

일단은 첫 번째 것만 바꿔도 시간이 많이 줄어듭니다

alftjd1 4년 전 0

1207koo님 감사합니다!

덕분에 시간초과 문제를 해결할 수 있었습니다!

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

문제

문제

출처

ICPC

시간초과가 발생합니다(파이썬)

alftjd1 4년 전 0

1207koo 4년 전 1

alftjd1 4년 전 0

1207koo님 감사합니다!

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말