[프로그래머스]소수찾기/python

👾(Lv.01)소수찾기
https://school.programmers.co.kr/learn/courses/30/lessons/12921

저번 문제에서 다뤘던 에라토스테네스의 체 알고리즘를 활용한다

🖥️ 답안

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

    for i in range(2,n+1):
        if i in num:
            num -= set(range(i*2,n+1,i))
    return len(num)

n=10이라고 가정

1. num = set(range(2,n+1))
   num= {2, 3, 4, 5, 6, 7, 8, 9, 10}

2. num -= set(range(i*2,n+1,i))
   현재 숫자 i의 배수들을 'num' 집합에서 제거

• i==2
  {4(=2x2),6(=3x2),8(=4x2),10(=5x2)}을 제거
• i==3{6(=3x2),9(=3x3)}를 제거
  이런 식으로 계속해서 남아 있는 가장 작은 수의 배수들을 제거

3. 마지막으로 return len(num) 을 통해 최종적으로 남은 소수들의 개수를 반환