YoungSoo

백준 - 골드바흐의 추측(9020 파이썬 풀이) 본문

코딩테스트

백준 - 골드바흐의 추측(9020 파이썬 풀이)

YoungSooSoo 2022. 12. 3. 22:33

제가 처음 푼 코드는 코드도 길고 시간도 오래 걸리는 코드였습니다.

def isPrime(a):
  if a<2:
    return False
  for i in range(2, int(a**0.5)+1):
    if a%i == 0:
      return False
  return True

t = int(input())
for _ in range(0,t):
  n = int(input())
  a=[]
  arr=[]
  if isPrime(n//2):
    print(n//2, n//2)
  else :
    for i in range(2, n):
      if isPrime(i):
        a.append(i)
    for i in a:
      if isPrime(n-i) and n-2*i>0:
        arr.append(n-2*i)
    if len(arr)>0:
      c = (n-min(arr))//2
      print(c, n-c)

먼저 소수를 구하는 isPrime 함수를 만들어줍니다.

그 뒤에 n을 2로 나눈 값이 둘 다 소수라면 n을 2로 나눈 값을 출력해주고 그렇지 않다면 소수를 모두 배열에 넣어두고

또한 소수이고 0보다 큰 수를 또 다른 배열에 넣어주고 제일 작은 값을 이용해 값의 차이를 구해 값을 도출했다.

 

다 풀고 더 간단한 코드를 찾기 위해 검색을 해봤는데 더 간단하게 풀 수 있는 방법이 있었다.

def isPrime(a):
  if a<2:
    return False
  for i in range(2, int(a**0.5)+1):
    if a%i == 0:
      return False
  return True

t = int(input())
for _ in range(t):
  n = int(input())
  b, c = n//2, n//2
  while b>0:
    if isPrime(b) and isPrime(c):
      print(b, c)
      break
    else:
      b -= 1
      c += 1

똑같이 값을 입력 받고 입력 받은 값을 2로 나누어 둘 다 소수이면 바로 출력해주고 아니라면 -1, +1씩 해주고 그 과정을
반복하는 코드가 있었다..