[백준] 4948번 베르트랑 공준 (Python)

문제

www.acmicpc.net/problem/4948

4948번: 베르트랑 공준

 

코드

import math

result=[]

def c(a,b):
    cnt=0
    check = [True] * (b+1) 
    
    for i in range(2,int(math.sqrt(b)+1)):
        if check[i] == True:
            for j in range(i*2, b+1, i):
                check[j] = False
    
    for i in range(a+1,b+1): # a보다 크고 b보다 작은 수를 구하기 때문에 3<x<7 x=4,5,6 3개
        if check[i] == True:
            cnt += 1
    return cnt

while True:
    a=int(input())
    if a==0:
        break
    result.append(c(a,2*a))
    


for i in result:
    print(i)

 

코드설명

입력된 수를 a라 하면 a 보다 크고 2a 작은 소수의 개수를 찾는 문제이다.

결국 소수구하기 문제인데 에라토스테네스의 체를 안쓰게되면 시간초과가 나기때문에 에라토스테네스의 체를 이용하여 풀었다. 

 

2부터 2a에 제곱근까지 for문을 돌리고 check가 true인 상태일때만 for문을 돌려 2,3,5 ... 배수들은 소수가 아니기 때문에 모두 false로 만들어 준다.

 

그리고 a~2a까지 True인 경우가 소수이다.