[파이썬python] 백준 1929번 - 에라토스테네스의 체

백준 1929번 소수 구하기 문제를 풀어보겠습니다.

코딩테스트를 처음 준비할 당시에 기초적인 문제들을 풀면서 이런 생각이 들었습니다.

소수구하기, 진수 변환하기 이런게 실제 코딩테스트에서 정말 나오는 걸까?

이런건 좀 넘어가도 되지 않을까? 더 어려운 그래프문제를 더 많이 푸는게 낫지 않을까?

그런데 이런 제 생각이 무색하게도 작년 카카오 블라인드 채용 코딩테스트에서

2번문제로 'k진수에서 소수 개수 구하기'라는 문제가 출제되었습니다.

그 문제를 보는 순간 띵 하더라고요. 뒤통수를 맞은 기분이였습니다.

 

그리고 그 이후에 다른 코딩테스트에서도

간간히 소수구하기가 첫번째 문제로

많이 출제가 되는 것을 직접 경험하였습니다.

 

물론 소수를 구하는 문제는 조금만 생각하면 금방 구현할 수 있습니다.

하지만 아마 코딩테스트에서는 대부분 시간초과가 날 것입니다.

그래서 검색을 해봤더니 에라토스테네스의 체라는 개념을 사용해야 한다는 것을 알게되었습니다.

 

만약 에라토스테네스의 체라는 개념을 모른 상태로 실전에서 소수 구하기 문제를 만났고,

열심히 구현을 해서 테스트케이스를 모두 맞았지만, 최종제출을 했을 때 시간초과가 난다면

정말 멘붕이 올겁니다. (하지만 어떤 코딩테스트는 틀렸는지 안 알려주는게 대부분이죠.) 

 

에라토스테네스의 체를 사용하여 소수 구하는 방법을 알아보겠습니다.

개념 자체는 쉬운데 이게 코드로 옮기는 과정을 이해하는게 저는 어렵더라고요.

저와 같은 어려움을 겪으시는 분이 있다면 도움이 되었으면 좋겠습니다.

 

그 전에 에라토스테네스의 체를 이용하지 않고 구해서 시간초과가 난 코드를 보여드리겠습니다.

n,m = map(int,input().split())

arr = [i for i in range(n,m+1)]

for i in arr:
    num=0
    for j in range(1,i+1):
        if i%j==0:
            num+=1
    if num == 2:
        print(i)

구현 아이디어는 소수는 1과 자기자신 밖에 나눠지는 수가 없다에서 가져왔고

1부터 자기자신까지 for문을 돌려서 나눠진 수의 개수가 2이면 소수라고 판단하여 출력하는 방식이였습니다. 

백준 1978번 소수찾기 문제에서는 이 구현 방식이 맞았기 때문에

이 문제에서도 맞을거라 예상했는데 결과는 시간 초과였습니다. 

 

그렇다면 에라토스테네스의 체가 무엇인지 설명드리겠습니다. 

일정 범위내 수열에서 배수들을 제거해 소수만 걸러내는 체를 에라토스테네스의 체라고 합니다.

범위의 제곱근까지만 약수의 여부를 검증하는 방식입니다. 

이렇게 되면 O(N)였던 시간복잡도가 O(N^(1/2))로 줄어들게 됩니다.

코드를 보면서 이해하도록 하겠습니다. 

n,m = map(int,input().split())

for i in range(2,int(m**0.5)+1):
	if prime_list[i]:
		for j in range(i*2,m+1,i):
			prime_list[j] = False

입력값 m에 해당하는 16을 코드에 대입하면 아래와 같습니다.

for i in range(2,5):
	if prime_list[i]:
		for j in range(i*2,17,i):
			prime_list[j] = False

i = 2일 때 4부터 16까지 2씩 늘어나면서 False처리합니다.

3	4	5	6	7
8	9	10	11	12
13	14	15	16

i = 3일 때 6부터 16까지 3씩 늘어나면서 False처리합니다.

3	4	5	6	7
8	9	10	11	12
13	14	15	16

i = 4일 때 8부터 16까지 4씩 늘어나면서 False처리합니다.

3	4	5	6	7
8	9	10	11	12
13	14	15	16

따라서 False처리되지 않은 3, 5, 7, 11, 13이 체에 걸러지게 되고,

소수인 값만 남게 되어 최종 답이 됩니다. 

 

정답코드)

n,m = map(int,input().split())

prime_list = [True]*(m+1)
prime_list[0] = False
prime_list[1] = False

for i in range(2,int(m**0.5)+1):
	if prime_list[i]:
		for j in range(i*2,m+1,i):
			prime_list[j] = False

for i in range(n,m+1):
	if prime_list[i]:
		print(i)

에라토스테네스의 체에 대해서 잘 이해가 되셨는지 모르겠습니다.

잘못된 부분이 있으면 댓글로 남겨주세요!

 

그럼 도움이 되셨다면 공감과 댓글 그리고 구독을 부탁드립니다.!!