백준 4948 번 문제 풀이 Python 파이썬 :베르트랑 공준

#68. 백준 4948번 문제 풀이: 베르트랑 공준

베르트랑은 임의의 자연수 n에 대해 n초과 2n이하의 소수는 최소 하나는 존재한다 했다. 자연수 n이 주어졌을 때, n보다 크고 2n이하인 소소의 개수를 구하라. 입력: 각각의 한 줄이 테스트 케이스이다. 마지막 표시로 0 이 입력된다. 출력: 각 테스트 케이스에 대해, n보다 크고 2n이하인 소수의 개수를 출력하라.

입력/출력

문제풀이+해설

소수는 1과 자신의 수 외에는 나누어지지 않는 1보다 큰 정수를 말한다. 예를 들어, 2, 3, 5, 7 ...
어떤 수가 소수 여부를 판단하려면, 2부터 자신보다 작은 수 까지 %(나머지) 연산을 해서 0으로 떨어지면 나누어지는 수가 있으므로 소수가 아니다.

주어진 범위에 해당하는 자연수를 확인해서 소수를 찾아내어 개수를 카운트해서 출력하면 된다.

여기서 주의할 것은 시간제한이 있다는 것이다. 일반적인 방법으로는 시간초과가 나타난다.
소수개수를 출력하는 케이스가 여러개 주어지기 때문에 그때마다 소수를 계산하는 것은 너무 비효율적이다.
그래서 미리 소수를 계산해 배열에 넣어두고, 요구하는 범위의 소수를 배열에서 가져오는 방식을 사용하면 된다.

code sol.

코드편집/실행

import math # sqrt 사용을 위해

# 소수 판별 함수 구현
def sosu(n):
  if n == 1: return False
  max_n = int(math.sqrt(n)) # 제급근까지만 나누어지는 수를 체크하면 됨.
  for i in range(2, max_n + 1):
    if n % i == 0: # 나누어 떨어지면 소수가 아님
      return False
  return True # 나누어 떨어진 수가 없으면 소수

# 소수 갯수를 찾는 케이스가 여러개 주어지므로,
# 속도를 위해 미리 리스트에 소수를 계산해 넣어 둔다.  
a_sosu = [] # 소수를 담아둘 리스트
for i in range(1, 123456*2+1): # 1부터 주어진 최대수 123,456 의 2n까지 계산해 둠.
  if sosu(i) == True: # 주어진 수가 소수이면.. 
    a_sosu.append(i) # 소수 리스트에 넣어둠
    
while True: # 무한루프
  n = int(input()) # 값을 하나씩 입력 받아 정수형으로 변환해서 대입
  if n == 0: # 0 값이 들어오면.. 
    break # 루프 끝냄.
    
  count = 0 # 소수개수 카운트
  n2 = n*2;
  for i in a_sosu: # 소수 목록에서 하나씩 가져옴
    if i > n2: break # 최대값보다 크면 현재 루프 끝냄
    if i <= n: continue # 최소값 이하면 건너뜀
    count += 1 # n, n2 사이 값이므로 카운트 증가
      
  print(count) # 소수 개수 출력