[Algorithm] 소수찾기

틀린 부분 또는 더 효율적인 접근법에 대해 피드백 주시면 감사하겠습니다!

---

Programmers 소수찾기

---

문제

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

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

입출력 및 예제

제한 조건

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

---

풀이

---

생각

• 당연히 모든 수를 다 나눠가며 소수를 구할 순 없다.
• 제일 직관적으로 해결할 수 있는 에라토스테네스의 체를 사용하자.

방법

• 모든 수를 소수 집합에 넣어놓자.
• 낮은 수부터 n까지 순회.
  • 당연히 2를 제외한 짝수는 소수가 아니므로, 제외한다.
  • 각 순회에서 현재 값의 배수가 소수 집합에 존재하면, 그 배수는 소수가 아니므로 집합에서 제거한다.
  • 이걸 계속 반복
• 결과적으로 소수집합에 남은 개수를 출력

유의

• 유의할 건 딱히 없어보이는데, 순회를 어떻게 돌지, 2를 제외한 2의 배수를 어떻게 빼고 순회할지 값을 잘 생각해야 한다.
• 소수집합에서 어떻게 뺄 것이냐를 잘 생각해야한다.
  • 여기서는 차집합을 사용했다.
  • C++은 set_difference를 사용하면 되고, Python은 set끼리 -를 통해 가능하다.

---

코드

---

def solution(n):
    s = set(range(3, n+1, 2))

    for i in range(3, n+1, 2):
        if i in s:
            s -= set(range(i*2, n+1, i))
    s.add(2)

    answer = len(s)
    return answer

---

느낀점

• Python으로 처음 풀기 시작했다.
  • For loop 등 코드 작성을 이렇게 짧게 할 수 있다니...!?
• Programmers는 풀어본지 얼마 안되서 사실 불편한 점이 많다. 제한시간 같은 점수의 영향을 미치는 제한이 없기 때문에 '이걸 어떻게 더 효율적으로 계산할'까 이런 고민을 못하게 만드는 것 같다. 하지만 또 좋은 점도 있다. 백준에서는 그냥 채점만 하지만, 여기선 효율성 채점을 따로 구성하고 있기도 하고 UI가 제일 맘에 든다.
• 다른 문제들도 많이 풀어봐야지

---

참조

• https://programmers.co.kr/learn/courses/30/lessons/12921