[PS] 230726 유형별 코테 준비

[PS]는 문제해결 및 알고리즘을 공부한 내용을 담고 있습니다.
문제는 백준 Online Judge, Leetcode에서 참고했으며, 본문에서는 문제 접근 방식과 새로 배운 내용을 담고 있습니다.

6588. 골드바흐의 추측

• 로직은 완성인데, 8%에서 시간 초과가 난다

• import math
  
  def isPrime(n):
      if(n%2==0):
          return False
      else:
          for i in range(2,math.ceil(math.sqrt(n)+1)):
              if(n%i==0):
                  return False
      return True
  
  while True:
      n = int(input())
      if(n==0):
          break
      a = 3
      b = n-3
      while(a<=b):
          if((isPrime(a)==True)and(isPrime(b)==True)):
              print("%d = %d + %d"%(n,a,b))
              break
          else:
              a += 2
              b -= 2
  

• 이렇게 하지 말고, 주어진 n이 있으니까 n에 대해 모두 prime을 계산해 배열에 저장해보기로 했다. 그 방법은 다음과 같다.
  • O(n)에 대해 실행
  • O(nlgn)에 대해 실행