[백준] 17103번 골드바흐 파티션 - 파이썬(Python)

https://www.acmicpc.net/problem/17103

17103번: 골드바흐 파티션

 

문제

 

접근법

 

1. 입력받은 수들 중 큰 수 구하기

2. 큰 수만큼  소수 구하기

3. 입력받은 수의 절반까지 안에서 소수들의 합 찾기

 

##시간초과가 나서 검색을 해봤는데 다들 내가 푼 풀이랑 똑같이 풀었다.

다른 게 있다면, 수들을 입력받을 때  append와 리스트에서 [-1]을 사용했다는 것이다.

 

때문에 혹시나해서

append 대신 미리 크기를 지정해서 대입을,

[-1]대신 대입을 사용했더니 시간초과가 안나게 되었다.

하나하나 사용함에 있어 조심해야 할 거 같고, 대입을 좀 더 많이 사용하도록 해야함을 느꼈다.

 

#기존 코드
import sys

T=int(input())
N=[]
maxN=0
for i in range(T):
    N.append(int(sys.stdin.readline()))

    if maxN<N[-1]:
        maxN=N[-1]
     
     
     
#변경 코드
import sys

T=int(input())
N=[0]*T
maxN=0
for i in range(T):
    _=int(sys.stdin.readline())
    N[i]=_

    if maxN<_:
        maxN=_

 

코드

import sys

T=int(input())
N=[0]*T
maxN=0
for i in range(T):
    _=int(sys.stdin.readline())
    N[i]=_

    if maxN<_:
        maxN=_

   
prime=[True]*(maxN+1)
prime[1]=False


for i in range(2,int(maxN**0.5)+1):
    if prime[i]:
        for j in range(i+i,maxN+1,i):
            prime[j]=False



for i in N:
    ck=0
    for j in range(2,i//2+1):
        if prime[j] and prime[i-j]:
            ck+=1

    print(ck)