[백준/4948] 베르트랑 공준 (with 파이썬)

✔ 문제

---

✔ 풀이

nums = [] # 소수를 저장할 리스트

for i in range(2, 246913): 
    for j in range(2, int(i ** 0.5) + 1):
        if i % j == 0:
            break
    else:
        nums.append(i)

while True:
    n = int(input())
    count = 0

    if n == 0:
        break

    for i in nums:
        if n < i <= 2*n:
            count += 1

    print(count)

---

✔ 설명

자연수 n이 주어졌을 때, n보다 크고, 2n보다 작거나 같은 소수의 개수를 구해야하는데 n을 입력받을 때마다 2n까지의 소수를 구하는 것은 시간이 굉장히 오래 걸린다.

그래서 2부터 246913의 범위에서 소수를 따로 배열에 미리 저장해 놓은 후 입력받은 n ~ 2n 사이의 소수가 배열에 얼마나 있는지 카운트하면 된다.

 

2부터 246913의 범위에서 소수를 찾는 이유는 n이 1부터 123,456까지 입력을 받을 수 있는 범위인데다 n~2n 사이의 소수를 구해야하기 때문이다. 그래서 1 * 2 <= n < = 123,456 * 2 + 1 범위에서 소수를 미리 찾아놓는 것이다.