[programmers] 프로그래머스 Level1 소수 찾기(파이썬 Python)

(주)그렙

 

[programmers] 프로그래머스 Level1 소수 찾기

(파이썬 Python)

 

* 문제출처 : 프로그래머스 코딩 테스트 연습, 알고리즘 문제

 

 

 

1) 문제

---

프로그래머스 level1 소수 찾기

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

 

 

2) 코드

---

def solution(n):
    is_prime = [True] * (n + 1)
    
    is_prime[0] = False
    is_prime[1] = False
    
    # 2부터 n까지 찾기
    idx = 2
    
    while ((idx * idx) <= n) :
        for i in range(idx * 2, n + 1, idx) :
            is_prime[i] = False
        
        idx += 1
    
    answer = is_prime.count(True)
    
    return answer

 

 

3) 풀이 과정

---

 

1. True가 담긴 리스트의 개수를 n+1개를 선언한다.

Why? n개가 아니라 n+1개를 선언한 걸까?

 

Answer) 마지막 인덱스n을 살리기 위해서다.

 

is_prime[2] = 2가 소수인지 
is_prime[11] = 11이 소수인지를 직관적으로 보기 위해서이다.

 

만약에 

is_prime[2] = 1이 소수인지 
is_prime[11] = 12가 소수인지 로 보게 된다면 복잡해지기 때문이다.

 

2. 리스트 인덱스 0번의 값은 0이 들어가기 때문에 False로 선언

 

3. 리스트 인덱스 1번의 값은 1이 들어가기 때문에 False로 선언

 

4. 리스트 인덱스의 2번의 값은 2가 들어간다. 이때부터 소수 찾기 시작.

 

 

 

 

 

 

5. while((idx * idx <=n )) 의 이해

 

 

 

 

 

ㄴ>1)소수를 찾는 게 아니라, 소수가 아닌 것을 판별한다. 그래서 일단 모두 True 처리한 것이다.

소수가 아닌 것만 False 처리하면 되니까.

 

ㄴ>2) 자연수 n에 대하여 2이상 루트 n이하의 자연수(1제외)로 떨어지게 되면, 그 수는 소수가 아니다.

 

Why? 2이상 루트n 이하의 자연수인가?

 

 

 

 

 

: n = 루트n * 루트n 은 이해가 될 것이다.

 

n = 루트n * 루트n = a * b를 보게 되었을 때

a * b로 표현할 수 있다는 얘기는, 즉 소수가 아니다 라는 말이 된다.

 

12의 경우 = 루트 12 * 루트 12로 표현이 되기도 하며,

2 * 6 혹은 3 * 4로 표현이 되기도 한다.

 

 

 

 

 

 

이와는 반대로

 

13의 경우(소수)는 루트 13 * 루트 13으로 밖에 표현이 되지 않는다.

 

 

n = 12일 경우(소수가 아닌 것)

12 = 루트 12 * 루트12 = a * b에서

 

 

 

a, b의 대소 관계를 보게 된다면

1) 루트 12 < a가 된다면, 루트12 > b가 된다.

 

 

 

a의 경우 활용할 수 있는 정보가 없다. 

b의 경우는 활용할 수 있는 정보가 있다.

 

 

 

 

즉 2, 3의 경우가 생긴다.(1은 소수가 아니기 때문에 생략)

 

 

 

루트 12의 이하의 자연수를 살펴보게 된다면(1 제외), 2와 3인 수가 있을 것이다.

12 % 2 = 0

12 % 3 = 0

이기 때문에, 이는 소수가 아니다.(False)

 

 

 

 

13의 경우 루트 13 이하의 자연수를 살펴보게 된다면, 

13 % 2 == 1

13 % 3 == 1

 

이기 때문에, 이는 소수다.(True)

 

 

 

정리하자면 while(idx * idx < = n)에서

idx * idx <= n은

자연수 n에 대하여 루트 n이하의 자연수를 의미한다.

루트로 표기하는 것을 idx로 사용하였다.

 

 

 

 

(idx)^2 = n 이면

idx = 루트 n이지 않은가?

 

 

 

 

 

즉, 위의 12의 예로 보자면 2와 3을 기준으로 2와 3은 살리고 이것들의 배수만 쳐내면 된다.

2와 3은 소수이지만

 

 

 

 

 

4,6,8,10은 소수가 아니며

6,9,12,15는 소수가 아니다.

 

 

 

 

 

 

 

< < 사고 과정 > >

---

 

주어진 수를 바탕으로 해당 수 까지 소수를 찾는 과정 - > 에라토스테네스의 체 사용

 

 

 

 

 

 

 

 

4) 정리 노트

---

: 우리는 직접적으로 어느 수가 소수가 판별 여부를 직접 이해할 수 있다.

 

하지만 컴퓨터가 소수를 이해하는 과정은 하나부터 열까지 손이 가기 마련이다.

 

또한 왜 이러한 알고리즘을 알아야 할까?라는 생각을 할지도 모르겠다.

 

하지만, 그럴 땐 하나만 기억하면 된다.

 

컴퓨터의 세계에 있어서 n이 100,000,000 혹은 그 이상의 수가 주어질 때마다

 

주어진 수를 시간 복잡도 측면과 공간 복잡도 측면에서 보다 효율적으로 처리하고자 보다 효율적인

 

문제 해결 방식이 주어진 것이다.

 

과거부터 지금까지 누군가 연구해온 자료는 활용하며 익숙해지기만 하면 된다. 학자가 될게 아니라면 우선 알고리즘을 받아들이자.