1일 N알고리즘 - #24

문제

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

9020번: 골드바흐의 추측

문제는 위 사이트를 참고해주세요.

 

---

풀이

primeList = [True] * 10001
for i in range(2, 10001):
    for j in range(i+i, 10001, i):
        if primeList[j] == True:
            primeList[j] = False
T = int(input())
for i in range(T):
    n = int(input())
    x = n // 2
    for j in range(x, 1, -1):
        if primeList[n-j] == True and primeList[j] == True:
            print(j, n-j)
            break

 

이번 문제는 시간 초과 때문에 고생했네요...

 

일단 한 번에 문제에서 지정해놓은 범위인 10000까지의 소수를 구합니다.

 

T에 테스크 케이스 개수를 저장하고

for문을 테스트 케이스 개수만큼 돌려줍니다.

n은  답을 구할 짝수입니다.

x는 n을 2로 나눈 몫입니다.

 

다시 for문을 돌리는데 이 때 범위를 x~1까지 주는데

x~2까지로 하면 n이 4일 때 값이 나오지 않습니다.

 

시작 범위를 2부터 하지 않고 n을 2로 나눈 값으로 시작하는 이유는

n이 나오는 두 소수를 찾으면 가장 나중에 나오는 조합?이 그 차이가 가장 작습니다.

예를 들어 n이 14일 때, 14보다 작은 소수는 2, 3, 5, 7, 11이고 조합은 3, 11 / 7, 7 --> 답은 7, 7입니다.

n이 20일 때, 20보다 작은 소수는 2, 3, 5, 7, 11, 13, 17, 19이고 조합은 3,17 / 7, 13 --> 답은 7, 13입니다.

 

그리고 if문으로 n-j값도 소수이고 j값도 소수인 수 들을 찾아 출력하면 답이 나옵니다.

 

---

결과

결과 화면