글 읽기 - 시간초과 질문드립니다!

black01676 1년 전 0

이전 소수관련문제들의 경우는 아래처럼

소수array를 boolean으로 나타낸 경우로 모두 해결했었습니다.

(동일한 알고리즘을 integer로 한 경우 실패하다가 저렇게 하니까 성공하더라구요ㅠㅠ)

사실 test case를 일단 전부 받은 후에 가장 큰숫자N을 기준으로 array를 먼저 만든후 재활용하고 싶은데

문제의 의도가 test case마다 출력해야하는 것 같아서 문제마다 array를 다시 만들고 있네요..

혹시 시간초과 해결 방법, 혹은 제가 잘못생각한 부분이 있을지 도움부탁드립니다!

T = int(input())

for i in range(T) :

    N = int(input())

    # 소수 array를 bool로 나타내기 (True : 소수)
    prime = [True]*(N+1)
    for ele in range(2, int(N**(1/2))+1) :
        if prime[ele] == True :
            i = 2
            while N >= ele*i :
                prime[ele*i] = False    #2이상 수의 배수면 False
                i+=1

    M = int(N/2)
    for i in range(M) :
        if (prime[M-i] == True) and (prime[M+i] == True) :
            print (M-i, M+i)
            break

cinador 1년 전 0

각 케이스마다 에라토스테네스의 체를 만들고 있습니다. 에라토스테네스의 체를 미리 만들고 테스트 케이스를 진행하시면 될거 같습니다.

black01676 1년 전 0

아~ input 조건 범위로 미리 만들어두면 되는군요 해보겟습니다! 감사합니다

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

문제

문제

출처

ICPC

시간초과 질문드립니다!

black01676 1년 전 0

cinador 1년 전 0

black01676 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말