[프로그래머스][Python] 12921 소수 찾기

12921 소수 찾기

문제 설명

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

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

제한사항

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

입출력 예

입출력 예 설명

입출력 예 #1

• 1부터 10 사이의 소수는 [2,3,5,7] 4개가 존재하므로 4를 반환

입출력 예 #2

• 1부터 5 사이의 소수는 [2,3,5] 3개가 존재하므로 3를 반환

🎯 풀이 과정

1. n까지 소수 찾기
2. 소수 어케 찾지 ? -> 에라토스테네스의 체

에라토스테네스의 체란?

• 고대 그리스 수학자 에라토스테네스가 발견한 소수를 찾는 방법이다. (위키백과 참고)

에라토스테네스의 체 알고리즘

1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다.

2. 2는 소수이므로 오른쪽 Prime Numbers에 쓴다.

3. 자기 자신인 2를 제외하고 2의 배수를 모두 지운다.

4. 남아있는 수 중 가장 작은 수인 3은 소수이므로 오른쪽 Prime Numbers에 쓴다.

5. 자기 자신을 제외한 3의 배수를 모두 지운다.

6. 남아있는 수 중 가장 작은 수인 5는 소수이므로 오른쪽 Prime Numbers에 쓴다.

7. 자기 자신을 제외한 5의 배수를 모두 지운다.

8. 남아있는 수 중 가장 작은 수인 7은 소수이므로 오른쪽 Prime Numbers에 쓴다.

9. 자기 자신을 제외한 7의 배수를 모두 지운다.

10. 위 과정을 반복하면 원하는 구간의 모든 소수를 구할 수 있다.

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

    return cnt


def test_sample():
    assert solution1(10) == 4
    assert solution1(5) == 3

다른 사람 풀이

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

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

같은 에라토스테네스의 체인데 내가 한 것보다 더 깔끔하게 작성하신 것 같다 ㅜ.ㅜ
한 수 배워갑니당 . .