백준 17103 - 짝[소수약수배수]

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

17103번: 골드바흐 파티션

 

 

배열의 i번째 소수만 참고해서 i와 N-i가 소수이면서, i와 N-i의 합이 N이 되는 경우의 개수를 찾으면 된다.

 

 

 

시간 초과난 코드 1

x=int(input())

for _ in range(x):
    n=int(input())
    ch=[0]*(n+1)
    for i in range(2,int(n**0.5)+1):
        if ch[i]==0:
            for j in range(i*2,n+1,i):
                ch[j]=1
    cnt=0
    for i in range(2,n//2+1):
        if ch[i]==0 and ch[n-i]==0:
            cnt+=1
    print(cnt)

 

매 입력값 마다 소수 리스트를 생성해서 시간 초과

 

정답 코드

x=int(input())

ch=[0]*(1000001)
for i in range(2,int(1000001**0.5)+1):
    if ch[i]==0:
        for j in range(i*2,1000001,i):
            ch[j]=1

for _ in range(x):
    n=int(input())
  
    cnt=0
    for i in range(2,n//2+1):
        if ch[i]==0 and ch[n-i]==0:
            cnt+=1
    print(cnt)

 

처음 소수 리스트를 완성 시킨 후 로직 수행