[알고리즘] 에라토스테네스의 체 with '프로그래머스 2단계 - 소수찾기 문제'

 

 

"에라토스테네스의 체"

 

알고리즘 문제, 특히 완전 탐색 유형을 풀다보면 아래와 같은 문제상황을 종종 마주친다.

 

1~n 사이에 있는 소수의 개수 구하기

 

 

보통 브루트포스를 통해 풀 수 있는데 레벨이 어느정도 되는 문제라면 시간초과가 발생하기 마련이다.

 

 

---

브루트포스(Brute Force)란?

 

직역하면 "무식한 힘" 이라는 뜻을 가진 알고리즘으로 무식하게 전체를 탐색하는 문제이다.

 

프루트포스를 사용하여 소수찾기 문제를 해결하면 아래와 같은 코드를 얻을 수 있다.

 

 

브루트포스 소수찾기 코드

def findSosuBF(n):
    sosuArr = []
    for i in range(2,n+1):
        cnt = 0
        for j in range(2,i):
            if i % j == 0:
                cnt+=1
        if cnt == 0:
            sosuArr.append(i)

    return sosuArr

print(findSosuBF(11))

 

다음 코드는 11의 소수를 찾는 브루트포스 소수 찾기 코드이다.

 

브루트포스 결과

물론 답은 정확하게 잘 나온다.

하지만 문제는 O(n) 이라는 시간복잡도에 의해, 만약 10억이라는 수 이하의 소수를 구하라는 명령을 내리면 너무나도 긴 시간이 필요하여 알고리즘 문제에선 '시간 초과' 오류를 직면할 수 밖에 없었다 😭

 

 

본인 또한 이와 같은 문제를 겪었고, 문제를 해결하기 위해 찾아낸 것이 '에라토스테네스의 체' 라는 알고리즘 방식이다!

 

우선 코드를 살펴보자!

 

---

에라토스테네스의 체 코드

def findSosuAT(n):
    check = [True] * (n+1)
    check[0],check[1] = False,False

    for i in range(2,int(n**0.5)+1):
        for j in range(i+i, n+1, i):
            if check[j] == True:
                check[j] = False
    
    return check

n = int(input())
check = findSosuAT(n)
sosuArr = []

for i in range(n+1):
    if check[i]:
        sosuArr.append(i)

print(sosuArr)

 

코드 설명

1. n+1개의 소수 판별 리스트를 생성한다.

 

2. 0과 1은 소수가 아니므로 소수 아님(False) 처리를 한다.

 

3. 2부터 n의 제곱근까지, 각 수의 배수를 소수 판별 리스트에서 소수 아님(False) 처리한다.

 

---

만약 n이 26이라면 아래와 같은 소수 판별 리스트가 만들어진다.

( 흰색:True / 회색:False )

 

이 소수 판별 리스트를 활용하여 아래와 같은 코드로 소수들을 구해낼 수 있다.

sosuArr = []
for i in range(n+1):
	if check[i]:
    	sosuArr.append(i)
        
print(sosuArr)

 

---

프로그래머스 '소수 찾기' 문제 - Python

 

본인은 이 문제를 풀기 위해 에라토스테네스의 체 알고리즘을 학습하였다.

 

위에서 설명한 알고리즘을 사용하여 아래와 같은 코드를 작성할 수 있었다.

 

설명은 위에서 다 했다고 생각되어 코드와 주석만 남기도록 하겠다.

 

 

import itertools

# 에라토스테네스의 체 알고리즘
# n+1개의 소수 체크 리스트 생성(모두 소수(True)인 것으로 초기화)
# 0,1은 소수가 아니므로 False로 변경

# 2부터 n의 제곱근 까지만 확인
# 2부터 n의 배수들을 소수가 아닌 것(False)으로 처리

# numbers로 만들 수 있는 수가 소수이면 answer+=1 (check[num] == True: answer+=1)
def findSosu(n):
    check = [True] * (n+1)
    sosuArr = []
    check[0],check[1] = False,False
    for i in range(2, int(n**0.5) + 1):
        for j in range(i+i,n+1,i):
            if check[j] == True:
                check[j] = False

    return check

def solution(numbers):
    answer = 0
    numArr = set()
    for i in range(1,len(numbers)+1):
        for n in itertools.permutations(numbers,i):
            v = int(''.join(n))
            if v in numArr:
                continue
            numArr.add(v)
    
    check = findSosu(max(numArr))
    
    for num in numArr:
        if check[num]:
            answer += 1
    
    return answer

 

 

reference

https://www.youtube.com/watch?v=9rLFFKmKzno&t=1s