백준 BaekJoon Online Judge // 9020

백준 알고리즘 BaekJoon Online Judge 9020번 "골드바흐의 추측" 문제입니다.

n=10000
a = [False,False] + [True]*(n-1) 
primes=[] 

for i in range(2,n+1): 
  if a[i]: primes.append(i) 
  for j in range(2*i, n+1, i): 
    a[j] = False

TC = int(input())
for tc in range(TC):
  N = int(input())
  K = 99999
  N1, N2 = 0, 0
  for i in range(2, N//2+1):
    if a[i] and a[N-i]:
      N1 = i
      N2 = N-i
  print(N1, N2)

에라스토테네스의 체를 활용하는 문제다.

 

그리고 이 문제는 소수리스트를 탐색하는 것이 아닌 소수인지 아닌지 리스트를 인덱스로 바로 접근하는 방식으로 문제를 풀었다.

 

소수 리스트를 전부 탐색하는 것은 시간 초과가 걸릴 수 있기 때문에(필자는 시간 초과에 걸렸었다) 반복문의 범위를 최대한 줄이고 탐색을 인덱스를 직접 찾아가서 소수인지 아닌지 확인하고 소수면 다음 과정을 진행하는 방식으로 문제를 풀었다.