글 읽기 - 시간초과... 무엇이 문제일까요

shumin 7년 전 0

단순한 소수 찾기 문제인데

시간초과로 인해서 pass를 못했습니다.

에라토스테네스의 체 알고리즘을 사용해야 하는건가요?

아니면 제가 다른 문제가 있는걸까요?

혹시 아시는분 답변 부탁드리겠습니다.

import math
#import time
 
def isPrime(_num):
    for i in range(2,round(math.sqrt(_num))):
        if(_num % i == 0):
            return False
 
    return True
 
if (__name__ == "__main__"):
    while(True):
#        start = time.time()                                                                                                                                                                                                                                                  
 
        num = int(input())
        if(num == 0):
            break
        else:
            prime_count = 0
            for i in range(num+1, num*2 + 1):
                if(isPrime(i)):
                    prime_count += 1
 
            print(prime_count)

sksdong1 7년 전 0

에라토스테네스의 체 알고리즘 사용하면 됩니다.

범위가 더 커졌을 경우 num~ 2*num사이의 수를 O(n) 에서 O(1)으로 줄이는 알고리즘도 고려해볼 수 있지만 여기까지 안해도 AC나오네요.

shumin 7년 전 0

아래와 같이 에라토스테네스 체 알고리즘을 적용했는데

아직 시간초과가 나오네요..

num ~ 2*num 의 소수의 수를 찾는 방법이 떠오르지 않아

2*num의 소수의 수 - num 의 소수의 수로 했는데 아직 시간초과가 발생합니다.

혹시 다른 조언 부탁드려도 가능할까요?

import math

def getPrimeNumberCount(_number):
#    print("Input Number : %d"%_number)
    data_list = []
    # Initialize the list
    for i in range(2,_number+1):
        data_list.append(i)

    for i in range(2, math.floor(math.sqrt(_number))+1):
        if(data_list.count(i) != 0): 
            for j in range(2*i, _number+1):
                if(j%i == 0): 
                    if(data_list.count(j) == 0): 
                        continue
                    data_list.remove(j)

#    print("The Prime Number : " + str(data_list))
#    print("The Total Number of Prime : %d"%len(data_list))

    return len(data_list)

if __name__ == "__main__":
    while(True):
        num = int(input())

        if(num == 0): 
            break

        n = getPrimeNumberCount(num)
        n2 = getPrimeNumberCount(2*num)
                                                                                                                                                                                                                                                                              
        print(n2-n)

sksdong1 7년 전 0

매번 구할 필요 없이 소수는 처음에 구해 놓으면 됩니다

어차피 소수의 수는 변하지 않죠..

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

문제

문제

출처

ICPC

시간초과... 무엇이 문제일까요

shumin 7년 전 0

sksdong1 7년 전 0

shumin 7년 전 0

sksdong1 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말