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

백준 4948번 베르트랑 공준 문제입니다.

 

n과 2n 사이에 적어도 소수가 하나 존재한다는 내용입니다.

 

이 문제는 1000 단위 정도까지는 일반적인 소수를 구하는 방식으로 하면 별 문제가 없지만

숫자가 커지면 일반적인 루프를 돌려 일일이 소수임을 판단해주는 방식으로는 시간제한에 걸리게 됩니다.

 

그렇기 때문에 제한조건을 활용하여 코드를 짜면 됩니다.

 

문제에서 제한조건은 1 <= n <= 123,456 이므로

2n의 범위는 2 <= 2n <= 246,912 가 됩니다.

 

그렇다면 2 ~ 246,912에 존재하는 소수를 미리 판별해 리스트에 저장해놓은 뒤

저희가 입력하는 숫자들이 지정하는 범위의 숫자들이 리스트에 몇개가 있는지 세어주기만 하면 됩니다.

 

이렇게 소수임을 판별하는 함수를 정의해주고

import math


def isPrime(x):
    c = int(math.sqrt(x)) + 1           # 합성수의 요소 최댓값은 sqrt(x) 보다 클 수 없다.
    if x == 1:
        return False
    else:
        for i in range(2, c):
            if x % i == 0:
                return False
    return True

 

그 이후 제한조건 범위에 존재하는 소수들의 리스트를 따로 만들어 줍니다.

a = list(range(2, 246912))			# 루프 돌면서 반복적인 소수판별 막기 위해 시작 전에 소수 리스트 만들고 시작


primeNum = []
for x in a:
    if isPrime(x):
        primeNum.append(x)

 

마지막으로 0이 입력되기 전까지 while문을 돌리며 반복해주는 코드를 짜주면 됩니다.

while True:
    count = 0
    n = int(input())
    if n == 0:
        break
    for i in primeNum:
        count += 1
    print(count)

 

이렇게 하면 10000 단위가 넘어가는 큰 숫자도 단수히 개수를 세어주는 문제이기 때문에 시간제한에 걸리지 않고 문제를 풀 수 있게 됩니다.

 

[전체 코드]

import math


def isPrime(x):
    c = int(math.sqrt(x)) + 1           # 합성수의 요소 최댓값은 sqrt(x) 보다 클 수 없다.
    if x == 1:
        return False
    else:
        for i in range(2, c):
            if x % i == 0:
                return False
    return True


# 루프 돌면서 반복적인 소수판별 막기 위해 시작 전에 소수 리스트 만들고 시작
a = list(range(2, 246912))


primeNum = []
for x in a:
    if isPrime(x):
        primeNum.append(x)

while True:
    count = 0
    n = int(input())
    if n == 0:
        break
    for i in primeNum:
        count += 1
    print(count)