[프로그래머스] Lv1 - 소수 찾기 (파이썬)

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

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

 

from math import sqrt


def solution(n):
    arr = [1] * (n+1)
    for i in range(2, int(sqrt(n))+1):
        if arr[i]:
            j = 2
            while i*j <= n:
                arr[i*j] = 0
                j += 1
    answer = arr.count(1) - 2
    return answer

 

에라토스테네스의 체
1. arr : 0부터 n까지의 리스트를 1로 정의
2. 2부터 n의 제곱근까지의 모든 i에 대해서
    - arr[i]가 1이면, arr에서 i의 배수를 전부 0으로 처리
3. arr에서 1의 개수 - 2를 반환 (-2를 해주는 이유는 0과 1을 제외하기 위해서)

 

숫자의 약수 성질을 이용해서 (n의 제곱근 + 1)까지만 판단을 하면 된다.

ex) 19 = 1, 19
int(19의 제곱근) = 4
19는 2,3,4의 배수가 아니라서 소수이다.

이를 에라토스테네스의 체에 적용을 하여 2부터 n의 제곱근까지의 수의 배수를 제거해가면서 탐색

ex) n = 19, int(n의 제곱근) = 4
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17
2의 배수 제거 : 1, 3, 5, 7, 9, 11, 13, 15, 17
3의 배수 제거 : 1, 5, 7, 11, 13, 17
4의 배수 제거 : (4가 이미 없으므로 스킵)
답 : 5, 7, 11, 13, 17 (1은 소수가 아님)

 

다른 사람의 풀이를 보던 중 집합의 차집합 성질을 이용한 풀이를 가져와 봤다.

from math import sqrt


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

 

에라토스테네스의 체
1. num : 2부터 n+1까지 집합으로 정의
2. 2부터 int(n의 제곱근)까지의 배수를 전부 제거
    - 차집합을 이용해서 num에서 2의 배수 집합을 제거
3. num의 길이 반환