[수학/소수] 백준 4948 베르트랑 공준 - Python

 

[ Contents ]

 

 

1. 문제 (링크 참조)

4948번: 베르트랑 공준

 

 

 

2. 문제 풀이

 n보다 크고 2n보다 작은 소수의 개수를 출력하는 문제입니다.

 

2022.02.08 - [Algorithm] - [Algorithm] 소수 판별 알고리즘, 에라토스 테네스의 체

[Algorithm] 소수 판별 알고리즘, 에라토스 테네스의 체

 최대 123457부터 246912까지의 소수 개수를 구해야 합니다. 단순히 하나씩 소수를 판정하면 시간초과가 뜹니다. '에라토스 테네스의 체'를 이용해서 소수를 판정해야 합니다.

 

 

 

3. 코드

import sys
input = sys.stdin.readline

# 에라토스 테네스의 체
def isPrime(n):
    primeList = [True] * n
    for i in range(2, int(n ** 0.5) + 1):
        if primeList[i]: # i가 소수라면
            for j in range(2 * i, n, i):  # 2i부터 n까지 i의 배수들은 False
                primeList[j] = False
    return [i for i in range(2, n) if primeList[i] == True] # 소수인 것만 리턴


while True:
    n = int(input())
    if n == 0: # 0 입력 시 종료
        break
    primeList = isPrime(2*n+1) # 2n까지 소수 판별
    cnt = 0
    for i in primeList:
        if i > n:
            cnt += 1 # n보다 큰 소수의 개수 세기
    print(cnt)

 에라토스 테네스의 체를 이용합니다. 해당 코드에 대한 설명은 위 링크의 '소수판별 알고리즘, 에라토스 테네스의 체'에서 보실 수 있습니다.

 2n까지 에라토스 테네스의 체로 소수판별을 하고, 그 중 n보다 큰 소수만 세서 출력합니다.