baekjoon 4948: 베르트랑 공준

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

4948번: 베르트랑 공준

---

에라토스테네스의 체 를 사용하여 주어진 값의 최대값까지의 소수를 찾고, 구간을 정해 소수가 몇개가 나오는지 확인하는 문제이다.

 

 

arr = []

# 입력
while 1:
    n = int(input())
    arr.append(n)
    if n ==0:
        break

# 에라토스테네스의 체 를 사용하여 소수를 찾음
Max=max(arr) *2
check = [0] * (Max +1)

for i in range(2,Max+1):
    # if not check[i]:
    #     pass
    for j in range(i+i, Max +1, i):
        check[j] = 1


for i in range(len(arr)):
    if arr[i] ==0:
        break
    cnt = 0
    st=arr[i] +1
    ed = arr[i]*2 +1

    for j in range(st,ed):

        if check[j]  ==1:
            continue
        else:
            cnt+=1
    print(cnt)