글 읽기 - 시간초과 입니다. 개선할 부분이 있는지 조언 부탁드립니다. (python)

dodi258 4년 전 0

숫자 n을 입력하면

n< x <= 2n 까지 숫자중에 몇개의 소수가 있는지 세는 문제입니다.

저는 n+1 ~ 2n 을 배열에 넣고, 소수가 아니면 배열에서 지워나가는 식으로 코드를 짜 보았습니다.

시간초과가 뜨는데, 여기서 개선할 수 있는 부분이 있거나 혹은 접근 방법이 잘못되었는지.. 조언 부탁드립니다.

import math
import sys

stop = False

while not stop:
    n = int(sys.stdin.readline()[:-1])
    prime_cnt = 2*n - n 
    
    # n+1 에서 2n까지 배열에 할당 
    numbers= [i for i in range(n+1, 2*n+1)]
       
    # 소수 판별 
    for i in range(2, int(math.sqrt(2*n)+0.5)+1):
        # 배열에 있는 수를 검사 
        for j in numbers:
            if (j != i) and (j % i == 0):
                # 소수가 아니면, 배열에서 제거
                numbers.remove(j)
                prime_cnt -= 1
            
    if n == 0:
        stop = True
        
    else:
        print(prime_cnt)

dodi258 4년 전 0

넵! 적용해서 해보겠습니당 감사합니다 !

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

문제

문제

출처

ICPC

시간초과 입니다. 개선할 부분이 있는지 조언 부탁드립니다. (python)

dodi258 4년 전 0

dodi258 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말