백준 [4948번] :: 베르트랑 공준 (Python , 파이썬)

www.acmicpc.net/problem/4948

4948번: 베르트랑 공준

 

 

처음 쓴 코드:

 

import math

def IsPrime(num):
    a = int(math.sqrt(num))
    if num == 1:
        return False
    else:
        for i in range(2, a+1):
            if num % i == 0: 
                return False
        return True

while True:
    n = int(input())
    cnt = 0
    if n == 0:
         break
    for i in range(n+1,2*n+1):
        if IsPrime(i):
             cnt += 1  
    print(cnt)

 

처음에는 위 문제를 접하고 너무 쉽다고 생각하여 코드를 막 적어보았다. 저번 1929번 문제랑 비슷하게 범위를 N보다 크고 2N보다 작은 범위로 설정하고 While 반복문으로 무한루프를 만들어 예제입력과 같이 1부터 10000까지 입력하고 0을 입력하였을때 종료하도록 하였다. 출력은 재대로 나왔지만 아니나 다를까 시간초과가 떳다. 

 

현재 코드는 N과 2N 사이의 숫자모두를 For문으로 소수인지 아닌지 하나씩 검사하고 있다. 이러면 코드가 매우 비효율적이라고 생각했다.

 

그래서 아예 주어진 n ≤ 123456 값에 있는 모든 소수를 리스트에 추가하여 리스트 안에서 N과 2N사이 소수를 카운터 하는 방식을 하기로 하였다.

 

 

결과 코드:

 

import math

def IsPrime(num):
    a = int(math.sqrt(num))
    if num == 1:
        return False
    else:
        for i in range(2, a+1):
            if num % i == 0: 
                return False
        return True

Num_list = list(range(2,246912))
Sort_list = []
for i in Num_list:
    if IsPrime(i):
         Sort_list.append(i)

while True:
    n = int(input())
    if n == 0:
        break
    cnt = 0
    for i in Sort_list:
        if n < i <= n*2:
            cnt += 1
    print(cnt)     

 

결과 코드를 작성하고 보니 처음 쓴 코드보다는 길어졌지만 시간을 줄이는데 성공했습니다. 위 코드도 시간을 효율적으로 사용했다고 못할 것 같습니다. 처음 쓴 코드도 되게 짧다고 생각했지만, 시간 초과가 뜨는걸로 봐선 공부를 많이 해야 할 것 같습니다.