글 읽기 - 파이썬 시간초과

kuy09085 2년 전 0

시간초과가 왜 나는지 모르겠습니다. 도와주세요 ㅠㅠ

import sys
input = sys.stdin.readline
def prime(a):
  if a == 1:
    return False
  else:
    for i in range(2,int(a**(0.5)+1)):
      if a % i == 0:
        return False
    else:
      return True

num =[]
for i in range(2,10001):
  if prime(i):
    num.append(i)
n = int(input())
list = []
for i in range(n):
  a = int(input())
  if prime(a//2):
    print(a//2,a//2)
  else:
    for j in range(2,(a//2)):
      if j in num:
        if (a-j) in num:
          list.append(j)
    print(list[-1],a-list[-1])
    list = []

bluejoyq 2년 전 1

10001까지의 소수를 담은 num 리스트의 길이는 1229인데 in을 이용해서 매번 수를 리스트에서 찾으시면 n의 시간이 걸려

for문 안의 in문까지 해서 n^2의 시간이 걸리게 됩니다. 5000^2이면 시간 초과가 납니다.

num리스트에 수를 인덱스로 넣었을 때 0과 1의 값으로 소수 여부를 판단하게 하면 됩니다. 아래 코드를 참조해주세요.

num =[0] * 10001
for i in range(2,10001):
    if prime(i):
        num[i] = 1
 

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

문제

문제

출처

ICPC

파이썬 시간초과

kuy09085 2년 전 0

bluejoyq 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말