[백준(BOJ)] 4948번 : 베르트랑 공준 - PYTHON[파이썬]

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

4948번: 베르트랑 공준

 

---

⊙ 문제

⊙ 입력

⊙ 출력

⊙ 예제 입출력

⊙ 알고리즘 분류

• 수학
• 정수론
• 소수 판정
• 에라토스테네스의 체

 

---

 

⊙ 문제 접근 과정

 

시간 초과가 괴롭혔던 문제. 해결 방법은 미리 소수 판별을 하면 된다.

 

❌

import sys

input = sys.stdin.readline

inputList = list()


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


while True:
    k = int(input())

    if not k:
        break
    inputList.append(k)

countList = [0 for _ in range(len(inputList))]

for i in range(len(inputList)):
    for k in range(inputList[i]+1, inputList[i]*2 + 1):
        if isPrime(k):
            countList[i] += 1

for i in countList:
    print(i)

 

첫 번째 풀이 코드다.

 

 

 

 

 

 

 

어떻게 해결할까 고민하다가 범위 제한인 1 <= n <= 123,456을 보고

에라토스테네스의 체를 미리 판별해놓으면 되지 않을까라고 생각했다.

 

그리고 그 범위만큼 bool list를 만들어 소수인지 아닌지 판별해주었다.

 

마지막으로 if문을 판별 범위만큼 돌려 바로바로 체킹해주어 시간 초과를 피할 수 있었다.

 

---

 

⊙ 문제 풀이

 

import sys

input = sys.stdin.readline

inputList = list()

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

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


def counting(inputValue):
    cnt = 0
    for k in range(inputValue+1, inputValue*2 + 1):
        if isPrime[k]:
            cnt += 1
    print(cnt)


while True:
    k = int(input())

    if not k:
        break
    counting(k)

 

---

⊙ 결과

 

---

⊙ 마무리

 

 

NONE

 

 

좋아요는 로그인하지 않아도 누를 수 있습니다!