[python] 백준 4948번

안녕하세요

오늘은 백준 - 베르트랑 공준 문제를 가지고 왔습니다.

문제 설명

해결 방법

문제를 해결한 방법은 다음과 같습니다.

1. 입력을 받기 전 입력의 최댓값의 2배인 배열을 만들어 0으로 초기화합니다.
2. 배열의 인덱스가 소수라면 배열의 요소를 1로 저장합니다.
3. 입력을 받아 n보다 크고 2n보다 작거나 큰 인덱스인 배열의 요소를 더해줍니다.

1. 입력을 받기 전 입력의 최댓값의 2배인 배열을 만들어 0으로 초기화합니다.

arr = [0 for i in range(2*123456 + 1)]

2. 배열의 인덱스가 소수라면 배열의 요소를 1로 저장합니다.

for i in range(2,2*123456 + 1):
    flag = 0
    for j in range(2, int(math.sqrt(i))+1):
        if i%j == 0:
            flag = 1
            break
    if not flag:
        arr[i] = 1

3. 입력을 받아 n보다 크고 2n보다 작거나 큰 인덱스인 배열의 요소를 더해줍니다.

while 1:
    cnt = 0
    n = int(sys.stdin.readline().strip())
    if n == 0:
        break
    for i in range(n+1, 2*n+1):
        cnt += arr[i]
    print(cnt)

전체 코드

import sys
import math

arr = [0 for i in range(2*123456 + 1)]
for i in range(2,2*123456 + 1):
    flag = 0
    for j in range(2, int(math.sqrt(i))+1):
        if i%j == 0:
            flag = 1
            break
    if not flag:
        arr[i] = 1


while 1:
    cnt = 0
    n = int(sys.stdin.readline().strip())
    if n == 0:
        break
    for i in range(n+1, 2*n+1):
        cnt += arr[i]
    print(cnt)