Algorithm/BaekJoon
백준 21.12.10 9020번 - 골드바흐의 추측
HappyFrog
2021. 12. 10. 18:16

def IsPrime(n):
seive = [True] * n
for i in range(2, int((n ** 0.5) + 1)):
if seive[i] == True:
for j in range(i + i, n, i):
seive[j] = False
return [i for i in range(2, n) if seive[i] == True]
primeNumbers = IsPrime(10000)
T = int(input())
for _ in range(T):
n = int(input())
for i in range(int(n/2), 1, -1):
if primeNumbers.count(i) != 0:
if primeNumbers.count(n - i) != 0:
print(i, n - i)
break
- 아리스토테네스의 체 함수를 그대로 사용하여 문제에서 주어진 범위만큼의 리스트를 미리 생성했습니다.
- 그 다음엔 주어진 n은 짝수이며 두 소수간의 차이가 가장 작은 값을 출력해야 하므로 2로 나누어 중간부터 1씩 줄여가며 값을 구하도록 반복문을 작성했습니다.
- 만약 i가 리스트에 존재하는 소수라면 (n - i) 의 값 또한 소수인지 판별하여 출력하도록 했습니다.