[Python] 4948번 베르트랑 공준

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

4948번: 베르트랑 공준

---

 

22/09/15

 

 

마찬가지로 그룹 채점 현황에 있는 무작위 문제 중 한 문제를 푼 것으로, 기존에 있던 에라토스테네스의 체 코드를 재활용하여 문제를 쉽게 풀었다.

 

---

 

문제 접근 방식:

 

 

문제가 n을 입력받으면 n과 2n 사이에 있는 소수의 개수를 출력하는 것이 문제이므로, 에라토스테네스의 체를 구현하면 될 것이라고 생각했다.

 

에라토스테네스의 체는 다음과 같이 구현했다.

 

먼저 크기가 정해진 배열을 1로 모두 초기화해준다. 이 배열의 인덱스는 숫자를 의미하며, 이 배열의 값이 만약 1이면 소수라는 뜻이고 0이면 소수가 아니라는 뜻이다.

 

이후 인덱스를 2부터 반복하면서 만약 소수라면(배열의 원소가 1이라면) 소수를 제외한 소수의 배수들을 모두 표에서 제외한다.(0으로 바꿔준다.)

만약 소수가 아니라면(배열의 원소가 0이라면) 넘어간다.

 

입력의 크기는 123456까지 오므로, 체의 크기는 123456*2 + 1로 정해주었다.(인덱스가 1부터 시작해야 하고, 2n사이에 있는 소수의 개수를 출력해야 하므로)

 

입력 전에 먼저 에라토스테네스의 체를 사용하여 만들어둔 다음 슬라이싱과 sum함수를 이용하여 개수를 구했다. 

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 4948번 베르트랑 공준
# 수학, 정수론, 소수 판정, 에라토스테네스의 체
num_li = [1]*(123456*2+1)
num_li[1] = 0
t = int((123456*2)**(1/2))
for i in range(2, t+1):
    if num_li[i]:
        for j in range(2*i, (123456*2+1), i):
            num_li[j] = 0

while True:
    n = int(input())
    if n == 0:
        break
    print(sum(num_li[n+1:2*n+1]))