글 읽기 - 에라테네토스의 채를 이용한 풀이인데.. 시간초과가 계속 나오네요..

aeromind 6년 전 0

먼저 입력받고 입력된 수의 max값보다 작은 소수 리스트를 구한뒤 출력하는 방식입니다.

아마도 그렇게 풀어야 하는 방식 같은데요.. 이상하게 시간초과가 계속 뜨네요.

어디가 문제인걸까요?

P=[2, 3, 5, 7, 11, 13, 17, 19,23,29,31,37,41,43,47,51]
import sys 
def core2(l):
    global P
    if l**0.5 >=P[-1]:
        core2(int(l**0.5))
    temp=set(range(P[-1],l+1))
    for i in P:
        #여기가? 
        temp-= set(range((P[-1]//i)*i,l+1,i))
    P+=sorted(set(list(temp)))
n=1
n_s=[]
while n:
    n=int(sys.stdin.readline())
    n_s.append(n)
core2(max(n_s))
for n in n_s:
    for i in P[1:]:
        if n-i in P:
            print('{} = {} + {}'.format(n,i,n-i))
            break

jh05013 6년 전 1

일단 소수 체가 시간 내에 돌아가긴 하는데, 너무 복잡합니다. 여기에 제가 쓰는 코드를 첨부합니다.

20줄의 n-i in P는 P를 쭉 훑어 보면서 n-i가 있는지 검사하기 때문에 매우 비효율적입니다.

sieve = list(range(n))
sieve[1] = 0
for p in range(2, int(n**0.5)+1):
    if sieve[p] != 0:
        for q in range(2*p, n, p):
            sieve[q] = 0

aeromind 6년 전 0

아 역시 n in list 문이 문제였군요.. 번지가 값인 방법이 좋네요. 감사합니다. ^^

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

문제

문제

출처

ICPC

에라테네토스의 채를 이용한 풀이인데.. 시간초과가 계속 나오네요..

aeromind 6년 전 0

jh05013 6년 전 1

aeromind 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말