글 읽기 - 시간초과가 나오는데 줄이는법 있을까요?

lalalaopera 1년 전 0

주어진 수까지 에라토네스의 체를 활용해서 리스트에 저장한뒤

작은 소수부터 빼고 그거에 대응하는 소수가 있는지 판별하는 방식으로 구해봤는데요.

vscode에서는 주어진 수보다 훨씬 큰수를 집어넣어도 금방금방 작동하는데 제출하면 시간초과가 걸리네요

import sys
num= int(sys.stdin.readline().rstrip())
for i in range (num):
  x = int(sys.stdin.readline().rstrip())
  a = [False,False] + [True]*((x)-1)
  primes=[]
  for i in range(2,x+1):
    if a[i]:
      primes.append(i)
      for j in range(2*i, (x+1), i):
          a[j] = False
  result= []
  for j in primes:
    if j <= x/2:
      if x-j in primes:
        result.append([j,x-j])
  print(result[-1][0], result[-1][1])

lalalaopera 1년 전 0

반으로 나눈거에 같은값만큼의 차를 찾는거로 바꾼뒤에도 시간초과가 나왔는데 소수 리스트를 제한값만큼 생성한후에 포문을 돌리니 시간초과는 안나오네요

import sys
a = [False,False] + [True]*(10001)
primes=[]
for i in range(2,10001):
  if a[i]:
    primes.append(i)
    for j in range(2*i, 10001, i):
        a[j] = False

num= int(sys.stdin.readline().rstrip())
for i in range (num):
  x = int(sys.stdin.readline().rstrip())
  result= []
  for j in range (int(x/2)+1):
    if x/2-j in primes and x/2+j in primes:
      print(int(x/2-j),int(x/2+j))
      break

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

문제

문제

출처

ICPC

시간초과가 나오는데 줄이는법 있을까요?

lalalaopera 1년 전 0

lalalaopera 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말