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

📌 문제

💯 정답

방법 1. 시간초과..

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

numbers = []

while True:
    n = int(input())
    if n == 0:
        for i in numbers:
            cnt = 0
            for j in range(i+1, (2*i)+1):
                if isPrime(j):
                    cnt += 1
            print(cnt)
        break
    else:
        numbers.append(n)

방법 2. 시간초과..

def isPrime(n):
    cnt = 0
    for i in range(n+1, 2*n+1):
        if i == 1:
            continue
        for j in range(2, int(n**0.5)+1):
            if i % j == 0:
                break
        else:               # for-else: for문이 break로 끊기지 않고 끝까지 수행했을 때 수행하는 코드
            cnt += 1
    print(cnt)

while True:
    n = int(input())
    if n == 0:
        break
    isPrime(n)

방법 3. 성공!!   "에라토스테네스의 체"

# 에라토스테네스의 체 부분 ---------------------------------------------
N = 123456 * 2 + 1
sieve = [True] * N		# sieve : '체' 라는 뜻

for i in range(2, int(N**0.5)+1):		# i로 절반만 검사
    if sieve[i]:
        for j in range(2*i, N, i):		# i의 배수를(index로 가지는) 모두
            sieve[j] = False			# False로 변경 (소수X)
# ----------------------------------------------------------------
def prime_cnt(n):
    cnt = 0
    for i in range(n+1, n*2+1):
        if sieve[i]:					# True 면
            cnt += 1					# 카운트
    print(cnt)

while True:
    n = int(input())
    if n == 0:				# 0 입력하면
        break				# 프로그램 종료
    prime_cnt(n)

📝 설명

• 방법 1. 과 방법 2. 는 모든 테스트 케이스마다 소수를 계산하는 게 시간 초과의 원인인 것 같다.
• 따라서, 문제에서 주어진 범위내의 소수를 모두 구해놓고 조건에 맞는 값만을 선택해 출력하기로 했다.
• 방법 3.은 특정 숫자까지의 모든 소수를 찾을 때 사용하기 좋은 소수 찾기 관련 알고리즘인 에라토스테네스의 체를 사용했다.

⭐️ 알고가기

👉 "에라토스테네스의 체" 설명 바로가기