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

 

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

4948번: 베르트랑 공준

1. 코드설명

자연수 n에 대하여 n부터 2n사이에 소수가 적어도 하나 존재한다는 내용

자연수 n이 주어졌을 때, n보다 크고, 2n보다 작거나 같은 소수의 개수를 구하는 문제

 

2. 예

3. 코드 내용

#  4948 : 베르트랑 공준
# 시간초과로 틀림
a = 1

def sosu(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:
    a = int(input())
    if a==0:
        break
    b = 0

    for i in range(a+1, 2*a+1):
        if sosu(i):
            b+=1

    print(b)

먼저 이코드는 python3로 제출했을 때 시간 초과로 틀렸다.

그래서 에라토스테네스의 체 풀이를 이용하여 다른 답 제출

 

check = [0]*2 + [1]*246912

for i in range(2, 246913):
    if check[i]:
        for j in range(i*2, 246913, i):
            check[j] = 0

while True:
    a = int(input())
    if a == 0:
        break
    
    b = 0
    print(sum(check[a+1:a*2+1]))

에라토스테네스의 체는 빠르게 소수를 구할 수 있는 방법이다.

리스트를 전부 1로 만들고 2부터 본인을 제외한 배수의 위치를 0으로 만드는 방법이다.

이방식으로 제한시간내에 체점이 가능했다.