[백준] 4948번 베르트랑 공준 파이썬 풀이 코딩테스트 연습 기본 수학2 실버2

문제 출처: https://www.acmicpc.net/problem/4948

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보다 작거나 같은 소수의 개수를 출력한다.

 

제한

• 1 ≤ n ≤ 123,456

 

예제 입력 1

1
10
13
100
1000
10000
100000
0

 

예제 출력 1

1
4
3
21
135
1033
8392

 

특정범위안에 소수를 구하는 문제입니다.

시간초과 때문에 오래걸렸네요... 베르트랑 공준의 개념을 잘몰라서 그랬던 것 같습니다!

 

arr = []

while True:
    num = int(input())
    target = num * 2
    cnt = 0
    if num == 0 or num > 123456:
        break
    elif num == 1:
        cnt +=1
        arr.append(cnt)
        continue
    
    for i in range(num, target+1):
        bool = True
        for j in range(2, int(i**0.5)+1):
            if i%j==0:
                bool = False
                break
        if bool == False:
            continue
        elif bool:
            cnt+=1

    if cnt !=0:
        arr.append(cnt)
        cnt = 0
  
print("\n".join(map(str, arr)))

첫번째 문제 풀이 시간 초과가 났습니다 아무래도 1초안에는 무리가.... ㅎㅎ

 

from math import sqrt
while True:
    n = int(input())
    if n == 0:
        break
    
    cnt = 0

    for i in range(n+1, 2*n+1):
        if i == 1:
            continue
        elif i == 2:
            cnt += 1
            continue
        else:
            for j in range(2, int(sqrt(i)+1)):
                if i % j == 0:
                    break
            else:
                cnt += 1

    print(cnt)

두번째 문제 풀이입니다.

구글링을 한번하고 작성하였는데도 시간초과가...? 비슷한 방법으로 정답이신분이 있어서 해봤는데 이 방법은 아닌가봐요

 

import math

def checkValue(n):
    if n == 1:
        return True
    else:
        for i in range(2, int(math.sqrt(number))+1):
            if n % i == 0:
                return False
    return True
 
value = list(range(123456*2))
prime_number = list()
 
for number in value:
    if checkValue(number):
        prime_number.append(number)

while True:
    num = int(input())
    cnt = 0
 
    if num == 0:
        break
 
    for value in prime_number:
        if num < value <= num*2:
            cnt += 1
    print(cnt)

세번째 만에 문제풀이에 성공하였네요 ㅋㅋㅋㅋ

 

구글링 제대로해서 코드를 거의 비슷하게 해보니 되네요

모르는 수학적기법이 나오면 검색을 해서 익힌다음에 문제를 풀어야겠어요

 

이제는 문제를 못푸는 것보다 시간초과가 많이 나오는 것 같아요.. ㅎㅎ