16. 소수 찾기

0. 문제

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

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

1. 알고리즘 계획

※ 처음에 문제의 어려움을 느끼고 알고리즘을 참고함.

1. True값을 가지는 리스트 생성
2. 찾고자 하는 값의 루트값 (sqrt, **0.5)에서 소수를 구한다. (# 에라토스테네스의 체 방법)
3. for문을 돌며, 소수인 경우를 찾으면 리스트에서 해당 값들을 False로 바꿈
4. 리스트에서 True값인 경우의 개수만 출력

2. 나의 코드

# 리스트와 True / False를 통해 문제를 간소화시킴
def solution(n):
    ls = [True] * (n+1)

    m = int(n ** 0.5) # 루트
    for i in range(2, m + 1):            # n의 최대 약수가 sqrt(n) 이하
        if ls[i] == True:             # i가 소수인 경우 
            for j in range(2*i, n+1, i): # i이후 i의 배수들을 False 판정
                ls[j] = False

    return len([i for i in range(2, n+1) if ls[i] == True])  # len()으로 개수 반환 / 개수만 필요하기 때문에

- 기존의 풀었던 방식은 호환성 문제에서 발목을 잡혔었으나, 위 방법을 통해 실행시간을 단축시킴

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)##sample

- set의 특징을 통해서 문제를 해결함

---

4. 정리 및 리뷰

- 온전히 자신만의 힘으로 하지 못한 부분이 아쉬었으나, - '에라토스테네스의 체'같은 방법에 대해 알지 못했었기에 어쩔 수 없었다는 생각을 함.

- 한 편으로는 파이썬의 여러 자료형의 특징과 활용법 등에 대해서 제대로 사용할 수 있게 해야겠다.

코드 만족도: ★★☆☆☆