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

1. 문제

 

2. 코드

import sys
import math

sosu = [0 for i in range(123457*2)]

sosu[1] = 0
sosu[2] = 1

for i in range(2, 123457*2):
    temp_i = int(math.sqrt(i))
    flag = 0
    for j in range(2, temp_i+1):
        if i%j == 0:
            flag = 1
            break
    if flag == 0:
        sosu[i] = 1
            
while 1:
    n = int(input())
    #n = int(sys.stdin.readline())
    cnt = 0
    if n == 0:
        break
    for i in range(n+1, 2*n+1):
        if sosu[i] == 1:
            cnt += 1
    sys.stdout.write(str(cnt))
    sys.stdout.write('\n')

 

3. 주요 포인트

숫자를 받고 그 수에 해당하는 소수를 계산하면 무조건 시간 초과난다.

미리 input제한만큼인 123456*2만큼 소수인지 아닌지 판단한 list(sosu)를 만들어놓고,

그 list에서 수만 세는 것이 포인트이다.

input의 제한이 강력할 경우, 미리 list를 만들어 놓고 판단하는 것이 빠르다는 것을 새겨놓자.