글 읽기 - 파이썬 시간초과 해결방법이 궁굼합니다

gik11kr 2년 전 0

시간을 어떻게 해야 더 줄일 수 있는지 궁굼합니다

def isprime(num):
    if num == 1:
        return False
    else:
        for i in range(2,int(num**0.5)+1):
            if num % i == 0:
                return False
        return True

all_num = [x for x in range(10001)]
prime_list = []

for i in all_num:
    if isprime(i):
        prime_list.append(i)


t = int(input())
for i in range(t):
    c,d=0,0
    n = int(input())
    for j in range(len(prime_list)):
        min = 10000
        for k in range(len(prime_list)-j):
            if prime_list[j] + prime_list[j+k] == n:
                a, b = prime_list[j],prime_list[j+k]
                if b - a < min:
                    c,d = a,b
    print(c,d)

cjfcjf 2년 전 0

모든 수에 대해서 isPrime 함수를 적용해서 소수를 판별하는 곳에서 시간이 많이 발생할 거 같네요
문제에도 적혀있듯이 에라토스테네스의 체를 적용해서 풀어보시는 걸 추천드립니다

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

문제

문제

출처

ICPC

파이썬 시간초과 해결방법이 궁굼합니다

gik11kr 2년 전 0

cjfcjf 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말