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

백준 4948

---

 

* 풀이과정

Think! 에라토스테네스의 체를 활용하여, 특정 범위 내의 소수들 또는 그 갯수를 구할 수 있다.

 

이전 개념 정리 글에서 특정 범위 내의 소수를 모두 출력했었다.

2024.01.22 - [파이썬/알고리즘] - 에라토스테네스의 체

이번에는 boolean 값으로 이루어진 리스트를 활용하여, 소수의 갯수를 구하였다.

 

 

1) True 값으로 이루어진 123,456 * 2 + 1 길이의 리스트 생성

2) 2부터 시작하여, 인덱스가 특정 수의 배수에 해당한다면 False 값 저장

3) n을 입력받아, n보다 크고 2n보다 작거나 같은 범위에서 True 값을 갖는 요소의 갯수를 구하여 출력한다.

 

# 리스트 생성, 초기화
is_prime=[True]*(123456*2+1)
is_prime[0]=False
is_prime[1]=False

# 2부터 시작하여, 해당 수의 배수인 경우 is_prime[j]=False로 저장
for i in range(2,len(is_prime)):
    if is_prime[i]==False: continue
    for j in range(2*i, len(is_prime), i):
        is_prime[j]=False


while True:
    num = int(input())
    # 0을 입력하면 종료
    if num==0:
        break
    
    # 소수의 갯수 초기화
    count = 0
    # 입력받은 값을 기준으로 특정 범위 내의 소수 갯수를 구함
    for a in range(num+1, 2*num+1):
        if is_prime[a]: count += 1
    print(count)