오늘 풀 문제는 골드바흐의 추측이다.
풀이 과정
우선 이 문제를 보고 제일 먼저 든 생각은 그냥 1부터 n까지 중에서 소수를 찾아서 리스트로 만들고 그 중에서 조합을 짜서 합이 n이 되는 걸 찾은 다음에 그 두 수의 차이가 제일 적은 걸 출력하면 되지않나? 해서 그렇게 짜보았다
from itertools import combinations
t = int(input())
def get_primes(n):
primes = []
for i in range(2, n):
primes.append(i)
for j in range(2, i):
if i % j == 0:
primes.pop()
break
return primes
for i in range(t):
n = int(input())
primes = get_primes(n)
# print(primes)
prime_combs = list(combinations_with_replacement(primes, 2))
# print(prime_combs)
min_diff = 10000
answer = ()
for prime_comb in prime_combs:
n1, n2 = sorted(prime_comb)
if n1 + n2 == n:
if n2 - n1 < min_diff:
answer = (n1, n2)
print(f"{answer[0]} {answer[1]}")
결과는 시간초과....
시간초과를 해결하기 위해 에라토스테네스의 체를 사용해봤다.
에라토스테네스의 체는 임의의 자연수 n에 대해 그 이하의 소수를 찾는 가장 간단하고 빠른 방법인데, for문을 돌면서 소수의 배수들을 삭제 시키는 식으로 동작한다. 자세한 건 아래 링크를 참고하면 된다.
그래서 get_primes 부분을 에라토스테네스의 체를 이용한 방식으로 변경해봤다.
def get_primes(n):
primes = []
sieves = [True] * (n + 1)
for i in range(2, n):
if sieves[i]:
for j in range(i * 2, n, i):
if sieves[j]:
sieves[j] = False
primes = [idx for idx in range(2, n) if sieves[idx] == True]
return primes근데 결과는 그래도 시간초과였다.... 🤯
아무래도 전체 조합을 다 구하는 데에서 시간초과가 난 거 같아서 다른 방법을 생각해 보기로 한다
엄청 쉬운 방법이 있었다!
그 수를 반으로 나눈 나음에 하나는 1씩 올리고 하나는 1씩 내리면서 그 두 수가 모두 소수면 그걸 출력하고 break를 거는 방법
최종 코드
t = int(input())
def isPrime(n):
for i in range(2, n):
if n % i == 0:
return False
return True
for i in range(t):
n = int(input())
n1, n2 = n // 2, n // 2
while True:
if isPrime(n1) and isPrime(n2):
print(f"{n1} {n2}")
break
n1 -= 1
n2 += 1
결과는 통과
결국 에라토스테네스의 체는 필요가 없었다..
그래도 에라토스테네스의 채에 대해서 한 번 더 배울 수 있었고, 두 수의 차이가 최소가 되면서 합은 n으로 일정하게 유지하는 방법에 대한 아이디어를 얻을 수 있어서 좋았다.
개발자