[프로그래머스] 소수 찾기 - Lv.1

[프로그래머스] 소수 찾기 - Lv.1 - [파이썬/python]

 

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

프로그래머스

---

 

1번 방법) 효율성은 조금 떨어지지만 가독성이 뛰어납니다.

- set을 활용해 차집합(- 빼기) 이용한 방법

---

# 프로그래머스 | 소수 찾기

def solution(n):

    #set을 쓰는 이유는 더하기 빼기할 때 편합니다.

    prime_nums = set(x for x in range(2, n+1))

    # 에라토스테네스의 체 알고리즘을 통해 소수 판별

    # 1. 처음 나오는 수는 나두고

    # 2. 처음 나오는 수의 배수는 싹다 제거

    for i in range(2, int(n ** 0.5) + 1):

        if i in prime_nums:

            prime_nums -= set(x for x in range(i*2, n+1, i))

   

    #개수 구하기

    count = len(prime_nums)

   

    return count

---

2번 방법) 효율성은 좋지만 가독성이 조금 떨어집니다.

- list의 인덱스를  활용해 True False를 변경하여 이용한 방법

---

# 프로그래머스 | 소수 찾기

def solution(n):

   

    # 0부터 n까지의 숫자 리스트 생성

    primes = [True] * (n + 1)

    primes[0] = primes[1] = False  # 0과 1은 소수가 아님

    # 에라토스테네스의 체 알고리즘을 통해 소수 판별

    # 1. 처음 나오는 수는 나두고

    # 2. 처음 나오는 수의 배수는 싹다 제거

    for i in range(2, int(n ** 0.5) + 1):

        if primes[i]:

            for j in range(i * i, n + 1, i):

                primes[j] = False

    # 소수 개수 세기

    count = primes.count(True)

   

    return count