글 읽기 - python / 시간초과

uyj0806 3년 전 0

이렇게 풀었는데 시간초과가 뜨네요.. 이 문제는 에라토스테네스의 체를 이용해서 풀지 않으면 못 푸는 문제인가요?

t = int(input())

for i in range(t):
  n = int(input())//2
  p1,p2 =0,0
  bias=0
  while n-bias>=2:
    sosu = True
    for j in range(2,n//2+1):
      if (n-bias) %j ==0 or (n+bias) %j ==0:
        sosu = False
    if sosu == True:
      p1, p2 = n-bias,n+bias
      print(p1, p2)
      break
    else:
      bias+=1

khanjhy 3년 전 1

네 에라토스테네스의 체를 이용하거나 그보다 시간복잡도가 더 작은 알고리즘을 쓰셔야 합니다

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

python / 시간초과

uyj0806 3년 전 0

khanjhy 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말