[소수] 백준 #4948 베르트랑 공준 - Python

🗂️ 문제

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

 

 

💡 접근법

n보다 크고, 2n보다 작거나 같은 소수의 개수를 구하는 문제이다.

이때 여러 케이스에 대해 소수를 판별할 때, 동일한 수에 대한 소수 판별 로직이 반복 수행될 수 있다.

 

이 과정을 없애고자 is_prime_num 리스트를 생성하여 한 번 소수 판별을 수행한 수에 대해서는 True or False로 값을 저장해두어 로직이 재수행되지 않도록 한다.

 

😎 내 코드

import sys

def is_prime(x):
    if x == 1:
        return False

    for i in range(2, int(x**0.5)+1):
        if x % i == 0:
            return False
    return True

is_prime_num = [None for _ in range(123456*2+1)]

while True:
    N = int(sys.stdin.readline())
    if N == 0:
        break

    cnt = 0
    for i in range(N+1, 2*N+1):
        if is_prime_num[i] is None:
            is_prime_num[i] = is_prime(i)

        if is_prime_num[i]:
            cnt += 1

    print(cnt)

 

✅ 정답 확인