Programmers/프로그래머스-소수 찾기-python

문제📖

풀이🙏

• 1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어라.
• 소수는 1과 자기 자신으로만 나누어지는 수를 의미한다.
  -> Sieve_of_Eratosthenes(에라토스테네스의 체)이론을 이용해 효율성을 극대화해 소수를 구하였다.
  -> len함수를 이용해 list의 총 개수를 반환하였다.

코드💻

# programmers, phase1 : 소수 찾기, python3
def solution(n):
    Sieve_of_Eratosthenes = [False, False] + [True] * (n - 1)
    result = []
        
    for i in range(2, n + 1):
        if Sieve_of_Eratosthenes[i]:
            result.append(i)
        for j in range(2 * i, n + 1, i):
            Sieve_of_Eratosthenes[j] = False
    return len(result)

최적코드

#  dalint , - , - , Jinsu Lim , 1stjstyle 외 388 명 님 코드 참고
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)

결과😎

출처 && 깃허브📝

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