글 읽기 - 파이썬) 여기서 시간을 더 줄일 수 있는 방법이 없을까요??

kangmj921 4년 전 0

partition구하는 부분에서 걸리는 시간을 줄여야 될 거 같은데 어떤 방식으로 해야 효율적으로 줄일 수 있을까요???

import math


def get_prime(N):
    max_length = math.ceil(math.sqrt(N))
    for k in range(2, max_length):
        if prime_number[k]:
            for i in range(k + k, N + 1, k):
                prime_number[i] = False
#입력값 N까지의 소수에 해당하는 index를 True로.

def find_partition(prime_number_list, N):
    i = int(N / 2)
    if prime_number_list[i]:
        return i
    else:
        for j in range(i, 1, -1):
            M = N - j
            if prime_number_list[j] and prime_number_list[M]:
                return j
#입력값 N을 기준으로 반을 나눠서 True의 값을 가지는 index를 찾고 partition을 구함.

T = int(input())
for k in range(T):
    n = int(input())
    if n % 2 == 0 and n > 2:
        prime_number = [True] * (n + 1)
        prime_number[0] = False
        prime_number[1] = False
        get_prime(n)
        X = find_partition(prime_number, n)
        print(X, n - X)

indioindio 4년 전 1

get_prime을 한 번만 (아예 10000까지 하거나, 입력의 최대값만큼 하거나)하면 더 빠를 것 같아요.

kangmj921 4년 전 0

와 2600ms에서 480ms로 엄청 많이 좋아졌네요 답변 감사드립니다~

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

문제

문제

출처

ICPC

파이썬) 여기서 시간을 더 줄일 수 있는 방법이 없을까요??

kangmj921 4년 전 0

indioindio 4년 전 1

kangmj921 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말