백준 4948번 베르트랑 공준 - Python

문제 링크 : https://www.acmicpc.net/problem/4948

이번 문제에는 저번에 풀어본 소수 구하기(1929번) 문제를 참고하면 된다.

풀이

범위 안에서 소수들의 개수를 구하면 되는데,
1. 소수를 구하는 함수를 만든다.
2. n < i <=2n 의 범위 안에서 소수를 찾으면 count += 1 을 해준다.
3. count를 출력한다.

처음에 문제에서 주어진 제한 범위 (1 ≤ n ≤ 123,456)를 무시하고 for문을 돌렸더니 시간초과가 되었다.
그래서 다른 분들의 블로그를 참고하여 (2 ≤ n ≤ 246,912) 만큼의 범위를 제한해주었다.

해답

import math
import sys

def num(num):     #소수 구하는 함수 (3 5 7 11 ...)
    if num == 1:  #1은 소수가 아니다.
        return False
    else :
        for i in range(2,int(math.sqrt(num))+1) :
            if num%i == 0:
                return False
        return True

all_list = list(range(2,246912)) # 문제에서 주어진 범위
save_list=[]

for i in all_list : # 주어진 범위 안의 소수들을 찾아서 저장해놓는다.
    if num(i):
        save_list.append(i)


num = int(sys.stdin.readline())

while num != 0:
    count = 0
    for i in save_list: # 저장된 소수들 중,
        if num < i <= num*2:
            count += 1
    print(count)
    num = int(sys.stdin.readline())