글 읽기 - 파이썬 시간초과

seonu2001 3년 전 0

4938번 문제 질문입니다.

소수 판별 할 때 제곱근까지 홀수로만 (2를 제외한 소수는 모두 홀수 이므로) 나누고,

n~2n까지 수 중에서도 홀수만 골라내어 소수판별을 했습니다.

그리고 input()대신 sys.stdin.readline()을 사용하기도 했는데

이래도 시간초과가 나네요.

1. 소스코드중 어디부분이 시간을 많이 잡아먹는거 같은지

2. 다른 효율적인 소수 판별법이 있는지

3. 소스코드 아쉬운점

알려주시면 정말 감사하겠습니다!

import math as m
import sys
def count_p(n):    #n초과 2n이하에서의 소수 갯수 구하기
    cnt=0
    if n==1 or n==2:    #n=1, 2일때 각각 만족하는 소수가 2, 3밖에 없으므로 1개
        return 1
    else:
        if n%2==0:    #n이 짝수일때
            for num in range(n+1,2*n+1,2):    #홀수인 부분만 판별
                temp=3
                while temp<=m.sqrt(num):    # 제곱근 까지만 홀수로만 나눔
                    if not num%temp:
                        break
                    temp+=2
                else:
                    cnt+=1
            return cnt
        else:    #n이 홀수일때
            for num in range(n+2,2*n+1,2):    #홀수인 부분만 판별
                temp=3
                while temp<=m.sqrt(num):    #제곱근 까지만 홀수로만 나눔
                    if not num%temp:
                        break
                    temp+=2
                else:
                    cnt+=1
            return cnt


Nums=[]    # 입력받은 값들
while True:    # 숫자 입력
    a=int(sys.stdin.readline())
    if not a:
        break
    Nums.append(a)
    
for N in Nums:    #n~2n까지 소수 개수 출력
    print(count_p(N))

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

문제

문제

출처

ICPC

파이썬 시간초과

seonu2001 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말