[python] 백준 17103 골드바흐 파티션
문제
에라토스테네스의 체로 푸는 문제 이긴 한데… 자꾸 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 계산이 실행되기 때문에 제 속도에 연산이 불가능하다는 것이다.
라이브러리며 함수며 그냥 좋다고 쓸 게 아니라 연산속도 등을 고려해서 써야된다는 경각심을 얻을 수 있었다.
결과