230127 에라토스테네스의 체, 파이썬 시간초과, 백준 6588번

 

 

 

 

 

 

from sys import stdin
from math import sqrt




while True:
	
	n=int(stdin.readline()) # n 입력
	if n==0:
		break

	prime_list = [True]*(n+1) # n까지 소수여부

    # 에라토스테네스의 체
	maxroot = int(sqrt(n))
	for i in range(3,maxroot+1,2): # 3부터 n의 최대약수가 될 수 있는 루트n까지 2씩 뛰면서 체크(짝수는 배제)
		if prime_list[i]: #i가 True라면=소수라면,
			for j in range(3*i, n+1, 2*i):
				prime_list[j] = False # 3i부터 m까지 2i씩 뛰면서 i의 배수는 다 소수아님.
	
    # 소수쌍 판별기
	for i in range(3, n//2 ,2): # 3부터 n//2까지 홀수들만 체크
		if prime_list[i] and prime_list[n-i]:
			print( f'{n} = {i} + {n-i}')
			break

 

 

에라토스테네스의 체를 사용해서 문제를 풀었고, 

완벽하다고 생각했는데도 시간초과가 뜬다.

왜인지 모르겠다. 잘 작동하는 데?

sys.stdin.readline()으로 받았고..

이중for의 소수판별이 아니라 에라토스테네스의 체도 제대로 사용했고...

 

2시간동안 이유를 찾다가 질문게시판에 글을 보고 답을 얻었다.

gyoseon123   

 

해당코드는 입력을 받고 매 반복마다 길이가 100만인 prime_array 배열을 매번 탐색하게됩니다. 테스트 케이스는 10만까지 주어질수있으므로

대략 100만 * 10만의 연산이 발생할 수 있어서 시간초과가 발생합니다. 

또한 소수를 담는 자료구조를 set을 사용하면 list보다 빠르게 어떤수가 소수인지 판별이 가능합니다. https://kyleyj.tistory.com/5

 

그렇다. 소수 판별과정을 while문 안에서 매 입력마다 반복하고 있던 것.

 

 

from sys import stdin
from math import sqrt

prime_list = [True]*1000001 # n까지 소수여부
prime_list[0]=False
prime_list[1]=False

# 에라토스테네스의 체 <- while문 밖에서 1회만 시행해야함
maxroot = 1000
for i in range(2,maxroot+1):
    if prime_list[i]: #i가 True라면=소수라면,
        for j in range(2*i, 1000001, i):
            prime_list[j] = False 


while True:
	
	n=int(stdin.readline()) # n 입력
	if n==0:
		break

    # 소수쌍 판별기
	for i in range(3, n//2 + 1 ,2): # 3부터 n//2까지 홀수들만 체크
		if prime_list[i] and prime_list[n-i]:
			print( f'{n} = {i} + {n-i}')
			break

# 시간초과 : https://www.acmicpc.net/board/view/108921

 

테스트케이스를 수행하기만 하는데 급급해

while문 안에서 모든 것을 수행하려했던게 패착이었다.