문제

image

에라토스테네스의 체로 푸는 문제 이긴 한데… 자꾸 time-out에 걸리고 만다.

시간초과 에러 

import sys
import math

input = sys.stdin.readline

n = int(input())

input_lst = []

lst = [True for i in range(1000001)]


def is_prime_number():
    lst[0] = False
    lst[1] = False
    for i in range(2,int(math.sqrt(1000001))+1):
        if lst[i] == True:
            j = 2
            while i * j <= 1000000:
                lst[i * j] = False
                j += 1
is_prime_number()

for _ in range(n):
    a = int(input())
    cnt = 0   
    for j in range(2,int(a//2)+1):
        if lst[a - j] and lst[j] :
            cnt += 1            
    print(cnt)

풀이

위에랑 큰 차이가 보이는가? 

import sys

t= int(input())

lst = [True for i in range(1000001)]


def is_prime_number():
    lst[0] = False
    lst[1] = False
    for i in range(2,1001):
        if lst[i] == True:
            j = 2
            while i * j <= 1000000:
                lst[i * j] = False
                j += 1
is_prime_number()

for _ in range(t):
    result = 0
    n = int(sys.stdin.readline().rstrip())
    for i in range(2,n//2+1):
        if lst[i] and lst[n-i]:
            result += 1
    print(result)

사실 문제 푸는 방법은 에라토스테네스의 체로 푸는 것이 맞다… 한참을 고민해도 답이 안 나왔는데, 단지 내가 놓치고 있었던 건 에라토스테네스의 체 함수 내 for 문 조건문에 있는 math.sqrt가 매우 무거운 연산이며 for 문의 조건문에 넣을 시에는 매 루프마다 sqrt 계산이 실행되기 때문에 제 속도에 연산이 불가능하다는 것이다.

라이브러리며 함수며 그냥 좋다고 쓸 게 아니라 연산속도 등을 고려해서 써야된다는 경각심을 얻을 수 있었다.

결과

image