글 읽기 - <Python> 시간 초과에 대해 질문있습니다

skyhp 4년 전 0

아래와 같이 에라토스테네스의 체를 이용하여 1부터 10000까지의 소수를 구하고

for문으로 m이 입력 받은 수 p의 절반부터 1까지 내려가면서

m과p-m이 모두 소수일때 두수를 출력하도록 하였는데 시간초과가 났습니다.

어느부분에서 오래걸리는 걸까요?

a=[k for k in range(1,10001)]
a.insert(0,0)
a[1]=0
for j in range(2,10000):
    l=2
    while j*l<=10000:
        a[j*l]=0
        l+=1
for i in range(int(input())):
    p=int(input())
    for m in range(p//2,1,-1):
            if m in a and p-m in a:
                    print(m,p-m)
                    break

djm03178 4년 전 0

리스트에서 in을 하는 연산은 리스트의 모든 원소를 돌면서 해당 원소가 있는지를 찾아야 하기 때문에 리스트의 길이에 비례하는 시간이 걸립니다.

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

문제

문제

출처

ICPC

<Python> 시간 초과에 대해 질문있습니다

skyhp 4년 전 0

djm03178 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말