[백준 1929 소수 구하기] set 함수 주의

과거의 블로그에 정리했던 소수 구하기를 응용하며 문제를 해결해보았다.

해결해야하는 문제는 다음과 같다.

www.acmicpc.net/problem/1929

1929번: 소수 구하기

 

 

이 문제는 그동안 소수 구하기 관련 글들을 많이 남겼었기 때문에 그를 바탕으로 작성하였었다.

처음에는 set 함수를 이용하여 에라토스테네스의 체 알고리즘을 이용하여 다음과 같이 작성하였다.

 

import math

m,n = map(int, input().split())
num = set(range(2,n+1))

for i in range(2,int(math.sqrt(n))+1):
    if i in num :
        num-= set(range(2*i,n+1,i))

for i in list(num) :
    if i >= m and i <= n:
        print(i)

 

 

하지만 set의 경우 list로 변환하였을 때  m부터 n까지의 소수를 순서대로 저장하지 않을 수 있다는 것을 알게 되었다.

따라서 오답이 떴다.

이를 극복하기 위해 list 로 변환 후 sorting 하는 작업을 수행하였다.

import math

m,n = map(int, input().split())
num = set(range(2,n+1))

for i in range(2,int(math.sqrt(n))+1):
    if i in num :
        num-= set(range(2*i,n+1,i))

list_num = list(num)
list_num.sort()
for i in list_num :
    if i >= m and i <= n:
        print(i)

 

아래와 같이 코드를 작성한 결과 통과가 떴다.

 

 

 

 

최근 보고 있는 책인  '이것이 코딩테스트다 with 파이썬 편_나동빈_한빛미디어' 에서도 작성한 코드가 있어서 아래에 정리해보았다.

www.hanbit.co.kr/store/books/look.php?p_code=B8945183661

이것이 취업을 위한 코딩 테스트다 with 파이썬

 

import math

# M,N 입력 받기
m,n = map(int, input().split())
array = [True for i in range(1000001)]
array[1] = 0 #1은 소수가 아니다

for i in range(2, int(math.sqrt(n))+1) :
	if array[i]:	#i가 소수인 경우(남은 수인 경우)
    	j=2
        while i*j <= n:
        	array[i*j] = False
           	j+=1

# M부터 N까지의 모든 소수 출력
for i in range(m,n+1) :
	if array[i] :
    	print(i)

 

알고리즘은 정말 많이 존재하기 때문에 여러 가지 시행착오를 해보면서 하나씩 익히는 것이 중요하다는 것을 알 수 있었다.✨