🌱 4948 베르트랑 공준 🌱

BOJ, 베르트랑 공준
사용언어 : python

1. 문제

베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다.

이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼프가 1850년에 증명했다.

예를 들어, 10보다 크고, 20보다 작거나 같은 소수는 4개가 있다. (11, 13, 17, 19) 또, 14보다 크고, 28보다 작거나 같은 소수는 3개가 있다. (17,19, 23)

자연수 n이 주어졌을 때, n보다 크고, 2n보다 작거나 같은 소수의 개수를 구하는 프로그램을 작성하시오.

2. 풀이

소수 문제다..!
지난 번 소수 문제에서 시간 초과를 겪고 에라토스테네스 체를 알게 됐었다.
(무작정 모든 수를 그 미만 수들로 나눠보는 아주 엄청난 코드를 짰었다는 소식ㅎㅎ)
그래서 문제를 보고 에라토스테네스 체를 사용해야겠다고 바로 생각했다!

📝방법 1 - 에라토스테네스 체

에라토스테네스 체를 이용하여 문제를 풀어보았다.

소수를 세는 함수를 따로 만들어서, 소수를 세는 변수 count를 만들어주고
소수 여부를 표시하는 prime_check라는 리스트를 만들어주었다.
(인덱스가 0부터 시작하기 때문에, 2의 소수 여부를 index가 2인 곳에 표시를 해주고 싶어서 길이가 num+1인 리스트를 만들었다.)

그리고 for문을 돌면서 해당 수가 소수라면 그 수의 배수들을 모두
prime_check에서 0으로 표시해주었다.
마지막에 prime_check에서 index 2부터 num까지 원소가 1일 때를 count해주면 끝!
(인덱스 0과 1은 0하고 1의 소수 판별 정보라서 필요 No!)

#해당 숫자 이하의 소수 갯수를 구하는 함수
def prime_count(num):
    #소수의 수를 세는 변수
    count = 0
    #소수 체크를 해주는 리스트
    prime_check = [1]*(num+1)
    #에라토스테네스 체를 이용한 소수 판별
    for i in range(2,num+1):
        if prime_check[i]:
            for j in range(i+i,num+1,i):
                prime_check[j] = 0
    #소수는 0,1은 해당하지 않으니깐
    for k in range(2,len(prime_check)):
        if prime_check[k]:
            count += 1
    return count

while True:
    #n이 0이 들어올때까지 입력 받기
    n = int(input())
    if n == 0:
        break
    print(prime_count(2*n)-prime_count(n))

물론 이 방법도 백준에서 정답으로 됐지만,
이전에 소수 문제보다 시간이 비효율적이라고 느껴졌다🤔
그리고 문제점을 바로 찾아서 바로 아래 방법으로 다시 풀었다..!

📝방법 2 -에라토스테네스 체 + 제곱근 이하 판별

문제를 다시 생각해보니, sqrt(num)보다 작거나 같은 애들로만 판별하면 됐다🤧
왜? 찬찬히 소수 판별 과정을 따라가보면!

어떤 수(k)가 소수가 되려면 1과 자기 자신을 제외하고는 나눠떨어지면 안된다.
그럼 2부터 k-1까지 수들로 나누어 떨어지지 않으면 되겠네?!
하지만 여기서 굳이 다 확인할 필요가 없다는 것이다!
k는 sqrt(k) 곱하기 sqrt(k) 또는 sqrt(k)보다 작은 수와 큰 수의 곱으로
나타낼 수 있다. 그렇기 때문에!
여기서도 num이하 친구들이 소수인지 확인 할 때, sqrt(num)이하
수들로 에라토스테네스 체를 해주면 되는 것이다!!!

def prime_count(num):
    count = 0
    prime_check = [1]*(num+1)
    for i in range(2,int(num**0.5)+1):
        if prime_check[i]:
            for j in range(i+i,num+1,i):
                prime_check[j] = 0

    for k in range(2,num+1):
        if prime_check[k]:
            count +=1
    return count

while True:
    n = int(input())
    if n == 0:
        break
    print(prime_count(2*n)-prime_count(n))

이렇게 고치고 돌리니, 시간이 훨씬 줄어들었다!