[백준] #4948 베르트랑 공준 python

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

4948번: 베르트랑 공준

 

📕 설명 📕

해당 문제를 풀이하기 위하여 "에라토스테네스의 체" 방법을사용하였다.

 

에라토스테네스의 체

 

위 방법은 A ~ B 사이 값 중의 소수를 얻고자 할 때 사용한다.

 

1. 2 ~ N 사이의 값을 담은 배열을 생성한다.

 

2. 배열 내 i 부터 시작하여, i의 배수들을 배열에서 지운다.

 

3. i의 배수들을 모두 지우면, i 다음으로 작은 배수들을 배열에서 지워준다.

 

4. 2, 3번을 반복할 수 있을 때까지 반복한다.

 

🧑🏻‍💻 나의 풀이 🧑🏻‍💻

 

def is_prime(n):
    arr = [True for i in range(n+1)]
    arr[0] = False
    arr[1] = False

    for i in range(2, n + 1):
        if arr[i] == True:
            j = 2
            while (i * j) <= n:
                arr[i * j] = False
                j += 1
    return arr

result_list = []
while True:
    A = int(input())
    if A == 0:
        break
    result = []

    arr = is_prime(2*A)
    A_arr = is_prime(A)

    result_list.append(arr.count(True) - A_arr.count(True))

for i in result_list:
    print(i)