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

4948번: 베르트랑 공준 (acmicpc.net)

4948번: 베르트랑 공준

베르트랑 공준

- 임의의 자연수 n에 대하여 n보다 크고 2n보다 작거나 같은 소수는 적어도 하나 존재한다. 

 

ex) 10보다 크고 20보다 작거나 같은 소수는 4개 {11,13, 15, 19}

      14보다 크고 28보다 작거나 같은 소수는 3개 {17, 19, 23}

 

자연수 n이 주어졌을 때 n보다 크고 2n보다 작거나 같은 소수의 개수를 구하는 프로그램 작성

 

[구조]
소수를 찾는 함수를 정의
주어진 범위에 함수 적용하여 소수만 골라내어 리스트에 저장
입력된 수가 리스트에 저장되어 있고 2*n 이하인지 확인하기 

# 베르트랑 공준
# 함수 정의 후 반복문에 집어넣기

def prime(m):
    if m == 1:
        return False
    for j in range(2, int(m**0.5 + 1)):  # m에 0.5제곱 = 루트
        if m % j == 0:
            return False
    return True


lst = list(range(2, 246912))  # 범위 제한
check = []

for i in lst:  # 해당 범위에서 소수만 따로 집어넣기 
    if prime(i):
        check.append(i)

while True:
    cnt = 0
    n = int(input())
    if n == 0:
        break
    for i in check:
        if n < i <= 2*n:  # 자신과 같은 수이면 안되므로 n에는 등호 넣지 않음.
            cnt += 1
    print(cnt)

왜 루트를 써서 하는지는 이 링크( 백준 4948번 파이썬 (velog.io))에 자세하게 설명되어 있다. 

친절한 인터넷 세상... 

굳이 지정 수까지 전부 다 돌 필요 없이 루트씌운 값까지만 돌아주면 훨씬 시간이 절약된다. 

 

처음에는 while문을 입력해놓고 그 안에 소수 판별 코드를 집어넣으려고 했다. 그런데 이렇게 하면 인덴트가 끝도 없이 들어가서 보기에도 안 좋고 코드를 짜는 나조차도 헷갈리게 돼서 전부 지우고 다시 생각했다.