백준 4948 베르트랑 공준

백준 링크:https://www.acmicpc.net/problem/4948

4948번: 베르트랑 공준

 

에라토스테네스의 체를 사용하면 간단하게 풀수있다.

import math


def is_prime_number(n,s):
    arr = [True for i in range(n+1)]

    for i in range(2,int(math.sqrt(n)+1)):
        if arr[i] == True:
            j = 2
            while i * j <= n:
                arr[i*j] = False
                j += 1
    for j in range(s+1):
        arr[j] = False

    return [i for i in range(2, n+1) if arr[i]]



while True:
    s = int(input())
    if s == 0:
        break
    else:
        n = s*2
        print(len(is_prime_number(n,s)))

arr로 배열을 전부 True로 설정한 뒤

최댓값 n의 int(제곱근)을 설정후 +1

만약 arr[i]가 True라면 arr안에있는 arr[i] 배수를 전부 False로 전환한다.

또한 문제 조건은 특정수 미만은 전부 제외이므로 계산이 끝났다면 다시 for in문을 돌려서 미만값은 False처리한다.