에라토스테네스의 체 | 프로그래머스 소수찾기 | 파이썬

프로그래머스 > 코딩테스트 > 알고리즘 고득점 Kit > 완전탐색 > 소수찾기 문제를 해결하기 위해 구글링을 하다가 '에라토스테네스의 체'를 알게 되었다.

'에라토스테네스의 체'는 수학에서 소수를 찾는 빠르고 쉬운 방법이다. 고대 그리스 수학자 에라토스테네스가 발견했다고 한다.

 

알고리즘은 아래와 같다. 

[참고] https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

 

 

이렇게 풀어 설명한 것을 보면 되게 쉽게 느껴지는 알고리즘이다. 하지만 이렇게 간단하게 생각하기까지가 참 어려운 것 같다...

 

 

아래는 python(3.6.4)으로 구현한 코드이다. 

def prime_list(n):
    # 에라토스테네스의 체 초기화: n개 요소에 True 설정(소수로 간주)
    sieve = [True] * n

    # n의 최대 약수가 sqrt(n) 이하이므로 i=sqrt(n)까지 검사
    m = int(n ** 0.5)
    for i in range(2, m + 1):
        if sieve[i] == True:           # i가 소수인 경우
            for j in range(i+i, n, i): # i이후 i의 배수들을 False 판정
                sieve[j] = False

    # 소수 목록 산출
    return [i for i in range(2, n) if sieve[i] == True]

 

sqrt(n), 즉 m 까지로만 나눠봐도 해당 숫자가 소수인지 알 수 있다.

 

여기서 시간복잡도는 O(sqrt(n)) 으로 줄어들게 된다.

 

** 1은 자연수 중에서 유일하게 소수도 아니고, 합성수도 아닌 수다. 

소수란? 양의 약수가 1과 자신뿐인, 1보다 큰 자연수, 즉 소수는 약수를 2개만 갖는다..

 

 

(수학이 지금에서야 발목을 잡을 줄이야... 쿠ㅜㅜ)

---

이 개념을 활용한 프로그래머스의 소수찾기 풀이 (구글링)

[문제링크]

프로그래머스

 

필요한 개념

- 순열? 

  서로 다른 n개의 원소를 가지는 어떤 집합에서 중복 없이 순서에 상관있게 r개의 원소를 선택하거나 혹은 나열하는 것

  ex) ["1", "7"] -> ("1"), ("7"), ("1","7"), ("7", "1")

 

- 조합?

  서로 다른 n개의 원소를 가지는 어떤 집합에서 중복 없이 순서에 상관없이 r개의 원소를 선택하거나 혹은 나열하는 것

  ex) ["1", "7"] -> ("1"), ("7"), ("1","7")

 

아래는 풀이 코드이다. 

from itertools import permutations

def solution(numbers):
    answer = []
    # 문자열 numbers를 각각 떼어내기
    nums = [n for n in numbers]
    per = []
    # 각 숫자 조합해서 순열로 만들기 ()
    # len(numbers)가 3개라면 1,2,3개를 순서상관있게 뽑는 각각의 경우의수, 순열을 구한다. 
    for i in range(1, len(numbers) + 1):
            per += list(permutations(nums, i))
    # 각각을 int형으로 변환
    new_nums = [int(("").join(x)) for x in per]
        
    for i in new_nums:
        if i < 2:
            continue
        check = True 
        for j in range(2, int(i ** 0.5) + 1):
            if i % j == 0:
                check = False
                break
        if check:
            # answer += i : Error ; 'int' object is not iterable
            answer.append(i)
            
    return len(set(answer))