[백준 알고리즘/Python3] 4948 베르트랑 공준

문제이해

n과 2n 사이에는 적어도 소수 하나는 존재합니다.

즉, 소수를 구하는 모듈이 있다면 n과 2n사이에 서 나온 소수들의 수만 구하면 됩니다.

 

n <  소수 <= 2n

 

코드

#소수를 구하는 함수
def prime_num(m,n):
    count = 0
    a = [False, False] + [True] * (n-1)

    #에라토스테네스의 체로 리스트a를 조정한다.
    for i in range(2, n+1):
        if(a[i]):
            for j in range(i*2, n +1, i):
                a[j] = False

    #리스트a가 True일 때 인덱스를 출력
    for i in range(m+1, n+1):  
        if(a[i]):
            count += 1
    return count

while(True):
    test_case = int(input())
    #0을 입력하면 종료
    if(test_case == 0):
        break

    count = 0
    count = prime_num(test_case, (test_case*2))
    print(count)

while문으로 계속 입력을 받습니다.

0을 입력하면 종료가 되죠

 

 

prime_num(시작 수, 마지막 수)메서드는 2개의 매개변수를 갖습니다.

 

시작점과 끝점을 매개변수로 가져와서 에라토스테네스의 체로 소수를 판별합니다.

 

주의할 점

 n과 2n사이의 소수를 찾는데

n < 소수 <= 2n 를 구해야 해서

 

에라토스테네스의 체로 걸러진 소수만 있는 리스트를 훑을 때 

시작점 +1 에서 시작합니다.