[BOJ/Python] 4948. 베르트랑 공준

📌 문제

https://www.acmicpc.net/problem/4948

4948번: 베르트랑 공준

 

📌 문제 접근 방법

1. is_prime이라는 배열을 만들고, 2부터 n의 제곱근까지를 탐색하며 소수의 배수를 모두 False로 바꿔준다.
2. n부터 2n까지 반복하여 해당 숫자가 소수라면 cnt를 1 더해준다.
3. n에 0이 입력되면 반복문을 종료한다.

 

📌 코드

# 백준 4948 베르트랑 공준
import sys
input = sys.stdin.readline


def is_prime_number(number):
    if number == 2:
        return True

    for x in range(2, int(number**0.5) + 1):
        if number%x == 0:
            return False
    
    return True


n = int(input())
while n:
    is_prime = [True for _ in range(2*n+1)]

    is_prime[0] = False
    is_prime[1] = False

    for x in range(2, int((2*n)**0.5) + 1):
        if is_prime[x]:
            if is_prime_number(x):
                mul = 2*x
                while mul <= 2*n:
                    is_prime[mul] = False
                    mul += x

    cnt = 0
    for i in range(n+1, 2*n + 1):
        if is_prime[i]:
            cnt += 1

    print(cnt)

    n = int(input())