백준 1929 [파이썬] 소수구하기 : 차집합 연산 활용

 

[Python] 백준 알고리즘 온라인 저지 1929번 : 소수 구하기

 

Python3 코드

import math

start_num, last_num = map(int, input().split())
nums = {x for x in range(start_num, last_num+1) if x == 2 or x % 2 ==1} # nums = 2와 홀수로 이루어진 집합

for odd_num in range(3, int(math.sqrt(last_num))+1, 2):  # 3부터 last_num제곱근의 범위에서 홀수만
    nums -= {i for i in range(2 * odd_num, last_num + 1, odd_num}
    # for문이 반복되는 동안 홀수의 배수로 이루어진 집합을 빼줌
    
for sosu in sorted(nums) :  
    if sosu > 1 :
        print(sosu)  # 오름차순으로 정렬해서 하나씩 출력

 

 

Python3 코드 풀이

 

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

이 문제는 두 개의 수를 입력받으면 두 수 범위 안에 있는 소수를 출력하는 문제이다. 이번 문제는 차집합 연산을 활용해서 소수가 아닌 수를 제거해나가는 방식으로 풀었다.

 

코드를 작성 할 때 집합 부분은 comprehension 표현식을 이용해서 한 줄로 작성하였다. 여러 개의 for문을 사용해서 코드가 길어고 차집합 연산을 하기 위해 변수 여러 개를 사용해야 하는 것이 오히려 가독성을 해치는 것 같아서 집합에 대해서만 comprehension 표현식을 사용하는 것으로 정해두고서 코드를 작성했다. 혹시라도 comprehension 표현식의 사용 예시를 보실 분들을 위해 이전에 작성했던 포스팅 링크를 걸어둔다. ▶ comprehension 표현식 사용 예시

 

2. 소수 구하는 코드 상단부, 2와 홀수로 이루어진 집합을 생성

start_num, last_num = map(int, input().split())
nums = {x for x in range(start_num, last_num+1) if x == 2 or x % 2 ==1} 
# nums = 2와 홀수로 이루어진 집합

 

두 수를 입력받고서 start_num, last_num으로 변수 이름을 지정하여 각각의 변수에 두 수를 선언하였다.

 

이후에 nums라는 집합을 생성하였는데 2를 제외한 모든 소수는 홀수이므로 2와 홀수로 이루어진 집합을 먼저 생성했다. 우선 range함수를 이용해서 start_num부터 last_num까지의 숫자 범위를 지정하고 그 안에서 if 조건식을 이용해 2와 홀수인 수들로 이루어진 집합을 구하였다. 

 

3. 소수 구하는 코드 하단부, 홀수의 배수로 이루어진 집합을 빼준다.

for odd_num in range(3, int(math.sqrt(last_num))+1, 2):  # 3부터 last_num제곱근의 범위에서 홀수만
    nums -= {i for i in range(2 * odd_num, last_num + 1, odd_num}
    # for문이 반복되는 동안 홀수의 배수로 이루어진 집합을 빼줌

홀수에는 소수가 아닌 수가 다수 포함되어 있다. 소수는 1과 자기 자신으로만 나눌 수 있는 수이다. 이 성질을 이용해서 홀수의 배수로 이루어진 집합을 생성하고 nums 집합에서 홀수의 배수 집합을 빼는 방식으로 코드를 작성했다. 

 

4. 처음에 시간이 오래 걸렸던 코드

import math

start_num, last_num = map(int, input().split())

for num in range(start_num, last_num+1):
    error = 0
    if num > 1 :
        for i in range(2, int(math.sqrt(num))+1):  
            if num % i == 0:
                error += 1
                break
        if error == 0:
            print(num)

 

숫자 리스트에서 하나씩 소수인지 아닌지를 확인하고서 소수이면 출력하는 코드를 처음에 제출했더니 시간이 오래 걸렸다. 이 이후에 숫자 집합에서 소수가 아닌 수를 제거하는 방식으로 코드를 바꾸었다.