💡문제접근
- 입력한 T개의 숫자 중에서 가장 최댓값을 구해 1부터 최댓값까지의 수 중에서 에라토스테네스의 체를 통해서 소수를 걸러내는 작업을 수행한다.
매 테스트케이스마다 에라토스테네스의 체를 돌리는 것보다 최댓값만 찾아서 그 범위까지 에라토스테네스의 체를 한 번만 시행해주면 시간을 확연히 차이가 나게 된다.
- 마지막으로 해당 짝수가 두 개의 소수의 합으로 표현이 가능한 경우를 찾을 때 구하고자 하는 개수보다 2배씩 증가되어 나왔는데 범위를 끝까지 돌려서 두 소수의 순서가 서로 다른 것도 다르게 계산이 되었다. 이 부분에서 많이 헤맸다. 절반으로 나눈 범위만을 탐색해서 순서가 다른 것을 세지 않게끔 설정해주면 된다.
💡코드(메모리 : 38228KB, 시간 : 2604ms)
import sys
input = sys.stdin.readline
T = int(input().strip())
num = []
max_num = -1
for _ in range(T):
N = int(input().strip())
num.append(N)
max_num = max(num)
arr = [True] * (max_num+1)
arr[0] = False
arr[1] = False
for i in range(2, max_num+1):
if arr[i]:
for j in range(i*i, max_num+1, i):
arr[j] = False
for i in num:
cnt = 0
for j in range((i//2) + 1):
if arr[j] and arr[i-j]:
cnt += 1
print(cnt)
📌 시간 초과 코드(TLE)
- 시간 초과 발생 원인 : 매 테스트케이스마다 에라토스테네스의 체를 시행해줘서 그런 것...?
import sys
input = sys.stdin.readline
def add(li):
return li[0] + li[1]
T = int(input().strip())
for _ in range(T):
N = int(input().strip())
arr = [True] * (int(1e6) + 1)
arr[0] = False
arr[1] = False
for i in range(2, N+1):
if arr:
for j in range(i*i, N+1, i):
arr[j] = False
li = []
for i in range(len(arr)):
if arr[i]:
li.append(i)
half = N // 2
cnt = 0
for i in range(half):
first = half - i
second = half + i
if first in li and second in li:
cnt += 1
print(cnt)
💡소요시간 : 47m