[파이썬] 4948 베르트랑 공준 feat 시간초과

요즘 하루에 몇 개씩 알고리즘을 다시 밀고 있다

 

작년에 이미 한 번 풀었던 문제들이라 비교적 쉽게 쉽게 잘 풀려가던 도중..

 

이상하게 안 풀리는 문제가 있다..

 

분명 작년에도 비슷한 코드로 푼 기억이 있는데.. 왜 계속 시간초과가 뜨는 걸까? 라면서 의아해하면서

 

인터넷을 좀 쳐보니.. 다들 풀이를 더 개량해서 더 빠르게 풀고 있었다 

 

 

기존의 코드는 

while 1:
    target = int(input())
    if target ==0:
        break
    cnt = 0 
    for ele in range(target+1, (2*target)+1):
        switch = False
        if ele<2:
            continue
        for j in range(2, round(ele**(1/2)+1)):
            if ele%j == 0:
                switch = True
                break
        if switch == False:
            cnt +=1
    print(cnt)

그냥 값을 받아와서 소수판별만 하고 cnt증가시키는.. 그런 코드를 썼는데 

이게 안 먹힌다

 

혹시나 해서 옛날 계정에 들어가서 똑같이 복사해서 그냥 재채점 해보니

똑같이 불합격이 뜬다..

 

결국 인터넷을 좀 찾아보고 나온 결론이 이 코드다

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

prime_ary = []
for i in range(2, 246912):
    if prime(i):
        prime_ary.append(i)

while 1:
    target = int(input())
    if target==0:
        break
    cnt = 0
    end = target*2
    for i in prime_ary:
        if target < i <=end:
            cnt+=1
    print(cnt)

 

prime함수는 언젠가 쓸듯해서 일단 따로 빼서 만들어주고

2부터 123456*2의 숫자만큼 소수를 만들어버린다 

 

그리고 그 만들어진 소수의 배열을 싹 돌려서 일치하는 값 안으로 값 비교를 한 뒤에

cnt를 출력한다

 

참..

 

기묘하다 1년 사이에 시간초과가 나느냐 안나냐는등.. 신기할 따름이다