[백준_4948] 베르트랑 공준

문제 보기: 4948번: 베르트랑 공준 (acmicpc.net)

4948번: 베르트랑 공준

문제

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

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

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

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

 

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 케이스는 n을 포함하는 한 줄로 이루어져 있다.

입력의 마지막에는 0이 주어진다.

출력

각 테스트 케이스에 대해서, n보다 크고, 2n보다 작거나 같은 소수의 개수를 출력한다.

 

새로 사용한 함수

range(param1, param2, param3)

param1: 레인지의 시작범위를 지정하는 매개변수 (0일때는 생략가능)

param2: 레인지의 마지막 범위를 지정하는 매개변수 (지정된 숫자 바로앞까지 레인지를 생성)

param3: 레인지의 간격을 지정하는 매개변수 (생략하면 기본값 1로 처리)

 

풀이 과정

코드1

 3번의 방식과 같이 함수화해서 소수를 먼저 찾아놓는 방식이다 여기서 다른점은 다른 트릭을 사용하지 않고 소수의 정의대로 만들되 루트의 개념을 1/2의 제곱인 것을 활용한 방식이라는 것이다.

 여기서 중요한것은 소수 판별을 수행할때 자기자신의 절반을 넘어가는 숫자를 수행할 필요가 없다는게 중요한 개념중에 하나이고 이것에서 심화된 개념이 제곱근이다 제곱근으로 처리해서 2~ 제곱근까지를 해보면 원래 값의 중간값정도를 가리키게 되어있다.

 이렇게 범위까지 정한 상태에서 range(a,b,c)를 사용해서 for문을 순회하게 되는데 이것은 예를 들면 2의 배수 3의 배수 4의 배수등에 접근해서 소거하는 방식으로 표현한 것이다.

이러한 방법을 에라토스테네스의 체 라고하며 나머지 수행 부분은 n의 값을 입력받아서 해당 값으로 리스트정보에 접근하고 해당 정보의 참거짓에 따라서 count 값을 변화시키는 방식으로 수행하였다.

 

 

코드2 : 시간초과

n을 입력 받은 상태에서 이 값보다 크고 2n까지의 범위에서 2보다 크고 자기자신보다 작은 수로 나눠주면서 나눠지면 소수라고 판별하고 check 플래그를 1으로 만들어주는 방법으로 구현

결과적으로는 이렇게 count를 하는 방식은 시간초과에 걸리게 됨

 

코드3 : 시간초과

함수화를 해서 미리 소수를 구해놓고 이것의 숫자를 세는 방식으로 구현 이것도 시간 초과

 

코드

코드1

N = 2*123456+1
prime_number = [True] * N

for i in range(2, int(N**0.5)+1):
    if prime_number[i]:
        for j in range(2*i, N, i):
            prime_number[j] = False

def check(n):
    count = 0
    for k in range(n+1, (n*2)+1):
        if prime_number[k]:
            count +=1
    print(count)
        
while i:
    n = int(input())
    if n == 0:
        break
    check(n)

코드2

# 소수 1과 나 자신만으로 나눌수 있는 숫자

# 특정 숫자가 소수인지 아닌지 판별을 하기위해 2부터 해당숫자 - 1 의 숫자들로 나누어 나머지가 0인지 확인
# 또한 나머지가 -인지 여러번 비교해야 하는데 그때마다 소수인지 아닌지 출력할

import sys

while 1:
    n = int(sys.stdin.readline())

    count = 0

    for i in range(n + 1, 2 * n + 1):
        check = 0
        for j in range(2, i):
            if i % j == 0:
                check = 1
                continue

        if check == 0:
            count += 1
    if n == 0:
        break
    print(count)

 

코드3

def check(check_value):
    if check_value == 1:
        return True
    else:
        for j in range(2, check_value):
            if check_value % j == 0:
                return False
    return True


prime_number = list()
value = list(range(123456 * 2))

for number in value:
    if check(number):
        prime_number.append(number)

while 1:
    user_num = int(input())
    cnt = 0

    if user_num == 0:
        break

    for num in range(user_num + 1, user_num * 2):
        if prime_number[num] == True:
            cnt += 1

    print(cnt)