백준 4948 [파이썬] 베르트랑 공준 : 차집합 연산 활용

 

[Python] 백준 알고리즘 온라인 저지 4948번 : 베르트랑 공준

 

Python3 코드

import math

# 소수의 집합을 구함
nums = {x for x in range(2, 246_913) if x == 2 or x % 2 ==1}
# nums = 2와 홀수로 이루어진 집합
for odd_num in range(3, int(math.sqrt(246_912))+1, 2):  # 3부터 최대값의 제곱근까지 홀수만
    nums -= {i for i in range(2 * odd_num, 246_913, odd_num) if i in nums}
    # 홀수의 배수로 이루어진 집합을 생성해서 빼줌

# 반복문 만들기
while True:
    n = int(input())
    if n == 0:
        break  # n == 0 이면 반복문을 끝냄
    sosu_list = [i for i in range(n+1, 2*n+1) if i in nums]
    # 소수 집합(nums)안에서 n보다 크고 2*n보다 작거나 같은 수의 리스트를 생성
    print(len(sosu_list))

 

 

Python3 코드 풀이

1. 코드 작성에 대한 전체적인 풀이 내용

이 문제는 n이 주어지면 n보다 크고 2n보다 작은 소수의 개수를 구하는 문제이다. 시간을 절약하기 위해서 소수의 집합을 먼저 구하고서 while 반복문으로 테스트 케이스를 입력받았다. 코드에서 리스트와 집합을 생성할 대는 comprehension 표현식으로 작성하였다. 혹시라도 comprehension 표현식의 설명이 필요한 분을 위해 이전 포스팅을 링크 걸어둔다. ▶comprehension 표현식 사용 예시

 

2. 코드 상단, 차집합 연산으로 소수 집합을 생성한다. 

nums = {x for x in range(2, 246_913) if x == 2 or x % 2 ==1}
# nums = 2와 홀수로 이루어진 집합
for odd_num in range(3, int(math.sqrt(246_912))+1, 2):  # 3부터 최대값의 제곱근까지 홀수만
    nums -= {i for i in range(2 * odd_num, 246_913, odd_num) if i in nums}
    # 홀수의 배수로 이루어진 집합을 생성해서 빼줌

입력받는 자연수 n은 123456보다 작거나 같은 수이다. 그래서 2부터 2n에 해당하는 246,913까지의 자연 수에서 소수를 먼저 구했다. 이렇게 입력될 수 있는 최대한도 범위 안에서 소수를 먼저 구해놓은 이유는 소수를 구하는 식은 시간이 오래 걸리기 때문이다. n을 입력받을 때마다 매번 2n까지 범위에서 소수를 구했더니 시간 초과가 되었다.

 

먼저 2와 홀수로 이루어진 집합을 생성했다. 소수에는 2 이외에는 짝수가 없기 때문이다. 이후에 3부터 최댓값의 제곱근까지 홀수를 반복하면서 해당 홀수의 배수로 이루어진 집합을 생성해서 빼주었다. 즉 처음 생성한 nums 집합의 차집합을 구하는 방법으로 소수의 집합을 구했다. set자료형인 집합의 차집합 연산에 대해서도 작성해둔 적이 있다. 혹시라도 필요하실 분을 위해 이전 포스팅 링크를 걸어둔다. ▶set자료형 합집합, 교집합, 차집합 사용 예시

 

3. 코드 하단부, 0이 입력될 때까지 while문으로 반복한다.

while True:
    n = int(input())
    if n == 0:
        break  # n == 0 이면 반복문을 끝냄
    sosu_list = [i for i in range(n+1, 2*n+1) if i in nums]
    # 소수 집합(nums)안에서 n보다 크고 2*n보다 작거나 같은 수의 리스트를 생성
    print(len(sosu_list))

테스트 케이스의 개수가 먼저 주어지지 않고 마지막에 0이 입력되면서 문제가 끝나기 때문에 while 반복문으로 작성하였다. if조건식으로 입력받는 수 n이 0인 경우 break로 반복문이 끝나도록 했다.

 

n보다 크고 2n 보다 작은 소수의 집합은 list comprehension 표현식으로 작성하였다. 먼저 range 함수로 n+1부터 2*n까지의 숫자 범위를 생성하고 in 연산자를 사용해서 위에서 생성한 소수 집합 nums 안에 포함이 된 수를 골라서 리스트를 생성하였다. 해당 리스트의 원소 개수는 len 함수로 구했다.