[프로그래머스] 소수 찾기(Level 1) / Python

문제주소 :programmers.co.kr/learn/courses/30/lessons/12921

코딩테스트 연습 - 소수 찾기

 

---

<문제 설명>

문제 설명

1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.

소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
(1은 소수가 아닙니다.)

제한 조건

• n은 2이상 1000000이하의 자연수입니다.

입출력 예

n                                                                        result

10	4
5	3

<풀이법>

▒ 한줄 개념: 에라토스테네스의 체 ▒ 

어떠한 n이 주어졌을 때 n보다 작은 소수를 찾으면 되는 간단한 문제입니다.

일반적으로 시도할 수 있는 방법은 두 가지가 있습니다.

 

1. 이중 반복을 이용한 탐색: 이중 반복은 O(n^2)의 시간복잡도로 굉장히 나쁜 효율성을 보여줍니다. 따라서 테스트에 통과할 수 없게됩니다.

2. 이중 반복이지만 제곱근까지만 나누기: 이번 문제를 풀면서 새로 알게된 방법인데, 어떤 수 n에 대해서 n의 제곱근까지만 나눌 경우 소수인지 아닌지 여부가 확인가능합니다.

 

하지만 두 가지 코드 모두 이 문제에서 테스트에 통과하지 못합니다. 1번의 경우 정확성테스트 조차 시간초과가 발생하고, 2번의 경우 효율성 테스트에서 시간 초과가 발생합니다.

 

따라서 여기서 이용해야하는 알고리즘이 "에라토스테네스의 체"입니다.

(에라토스테네스의 체 (위키백과)):ko.wikipedia.org/wiki/에라토스테네스의_체)

출처: 위키백과

과정을 설명하면 현재 숫자들 중 가장 작은 수를 소수라 가정하고 그 수의 배수를 모두 소수가 아니라고 체크하는 것입니다. 그리하여 최종적으로 소수들만 뽑아낼 수 있는 방법입니다.

 

1. 1은 소수가 아니므로 2부터 확인

2. 현재 가장 작은 수:2 -> 2의 모든 배수 False 체크

3. 체크 안된 가장 작은 수:3 -> 3의 모든 배수 False 체크

4. 체크 안된 가장 작은 수:5 -> 5의 모든 배수 False 체크

5..... n에 도달할 때까지 반복

 

이렇게 진행할경우 기본적으로 반복문 O(n)의 시간에, 해당 소수의 배수에 대해 접근하는 것은 인덱스로 접근하여 map의 시간복잡도가 O(1) 이므로, 기존의 두 가지 방법보다 시간적인면에서 월등히 좋습니다. 

 

따라서 에라토스테네스의 체 방식을 이용해서 문제를 풀어야만 통과할 수 있게 됩니다.

<코드(Python)>

def solution(n):
    check = [False] *2 + ([True] * (n-1))
    for i in range(2, n+1):
        if check[i]:
            for j in range(i*2, n+1, i):
                check[j] = False

    return check.count(True)

 

 

더 많은 코드 보기(GitHub) : github.com/dwkim-97/CodingTest