글 읽기 - 시간 줄이는 방법좀요....

wjsalsdn16 2년 전 0

a 범위 조건으로 break 시켜서 시간을 단축해도 시간초과가 뜨네요 ㅜㅜ

도와주세요

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



T = int(input())

for _ in range(T):
    
    a = int(input())
    result = []
    
    for i in range(len(primes)):
        if primes[i]<=a :
            for j in range(len(primes)):
                if primes[j]<=a :
                    if primes[i]+primes[j] == a :
                        if primes[i]-primes[j]>=0:
                            result.append(primes[i]-primes[j])
                    
                        else:
                            continue
                    else:
                        continue
                else:
                    break
        else:
            break

        
            
    for i in range(len(primes)):
        if primes[i]<=a:
            for j in range(len(primes)):
                if primes[j]<=a:
                    if primes[i]+primes[j] == a :
                        if min(result) == primes[i]-primes[j]:
                            print(primes[j],end=' ')
                            print(primes[i])
                            break
                    else:
                        continue
                else:
                    break
        else:
            break

seungwuk98 2년 전 1

일단 에라토스 테네스의 체의 첫번째 반복문은 루트 n까지 돌리는 것이 맞습니다. 반복분 수정하시고

아래 반복문 첫번째 덩어리에서 두번째 반복문은 i부터 시작해주면 중복되는 경우를 줄일 수 있습니다.

밑에 반복분 덩어리 2개중 뒤의 것은 지울 수 있습니다. 이 부분은 직접 생각해보시기 바랍니다.

seungwuk98 2년 전 1

그리고 사실 반복문 1개면 충분합니다.

wjsalsdn16 2년 전 0

어흑..... ㅜㅜㅜ 감사합니다 덕분에 도움 많이 됐어요

아직 전 멀었습니다

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

문제

문제

출처

ICPC

시간 줄이는 방법좀요....

wjsalsdn16 2년 전 0

seungwuk98 2년 전 1

seungwuk98 2년 전 1

wjsalsdn16 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말