[Python] 백준 알고리즘 9020번 : 골드바흐의 추측

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

9020번: 골드바흐의 추측

 

 

 

 

 

👩‍💻입력한 숫자까지의 소수 list 만들기 -> 골드바흐 파티션만 추출

-> 차이가 가장 작은 조합 출력 : 시간초과☠️

 

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

n = int(input())
for i in range(n):
  num = int(input())
  primeLi = []
  for i in range(2,num):  
    if isPrime(i):
      primeLi.append(i)
  res = []
  for i in primeLi:
    for j in primeLi:
      if i < num and j < num and i + j == num:
        res.append([i,j])
  index = 0
  for i in res[0:int(round(len(res)/2))]:
    min = 0
    if abs(i[0] - i[1]) >= min :
      min = (abs(i[0] - i[1]))
      index += 1
  print(res[index-1][0], res[index-1][1])

 

def isPrime(num):
  if num == 1:
    return False
  else:
    for i in range(2, int(num**0.5) +1):
      if num % i ==0:
        return False
    return True
    
# 소수일 때 True를 반환해주는 함수 
# 소수만 찾아주는 함수

 

n = int(input())
# 테스트 케이스 개수 입력받기
for i in range(n):
  num = int(input())
  # 짝수 n 입력받기
  primeLi = []
  # 짝수 n보다 작은 소수 list
  for i in range(2,num):  
    if isPrime(i):
      primeLi.append(i)
  res = []
  # 짝수 n보다 작은 소수들 중 합이 n이 되는 소수들[i,j] list
  for i in primeLi:
    for j in primeLi:
      if i < num and j < num and i + j == num:
        res.append([i,j])
  index = 0
  for i in res[0:int(round(len(res)/2))]:
    min = 0
    if abs(i[0] - i[1]) >= min :
      min = (abs(i[0] - i[1]))
      # 차의 절댓값이 가장 작은 list 출력
      index += 1
  print(res[index-1][0], res[index-1][1])

 

 

👩‍💻입력한 숫자의 중간값으로 부터 1씩 커지고 작아지면서 둘다 소수일 때 출력 : 성공🌈

 

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

n = int(input())
for i in range(n):
  num = int(input())
  for i in range(0, int(num//2)):
    if isPrime(int(num//2) + i) and isPrime(int(num//2) - i):
      print((int(num//2) - i), (int(num//2) + i))
      break;

 

n = int(input())
for i in range(n):
  num = int(input())
  for i in range(0, int(num//2)):
    if isPrime(int(num//2) + i) and isPrime(int(num//2) - i):
      print((int(num//2) - i), (int(num//2) + i))
      # 중간값 에서 i를 빼고 더한값이 모두 소수일 때 출력
      break;

 

 

 

🚀결과🚀

 

 

 

✨Point✨

1. 소수 판별할 때는 함수를 미리 만들어놓고 사용하면 편리!
2. 합이 주어질 때 차이가 가장 적은 두수는 (중간값+i) , (중간값-i)