글 읽기 - 파이썬 시간초과 뭐죠 ..?

kjy910116 1년 전 0

이상하네요 ..

시간초과라니.. 1929번도 통과한 함수식인데 ㅠㅠ

혹시 뭐가 잘못되었을까요 ?

def isPrime(num):
    if num==1:
        return False
    else:
        for i in range(2, int(num**0.5)+1):
            if num%i == 0:
                return False
        return True

while True:
    n = int(input())
    if n == 0:
        break
    else:
        temp = []
        for i in range(n+1, 2*n+1):
            if isPrime(i):
                temp.append(i)
        print(len(temp))

djm03178 1년 전 1

1929번은 범위 내의 소수들을 딱 한 번만 구하면 됩니다.

이 문제는 테스트 케이스가 여러 개입니다. 이 코드와 같은 방법을 통해 넓은 범위의 소수를 구하는 것은 다소 비효율적인데, 이를 테스트 케이스의 수만큼 반복하기에는 무리가 있습니다.

에라토스트테네스의 체 등을 이용하여 한 번만 소수 목록을 구한 뒤 이후로는 빠르게 소수 체크를 하는 방법을 사용해야 합니다.

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

문제

문제

출처

ICPC

파이썬 시간초과 뭐죠 ..?

kjy910116 1년 전 0

djm03178 1년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말