[Py_Lv1] 소수찾기

문제 설명

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

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

제한 사항

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

입출력 예

접근법

여러가지 방법으로 해결해보려고 노력했으며 가장 기본적인 방법으로 해결을 하였습니다.

하지만, 더 최적에 방법이 있다는 것을 알게되었고 [에라토네스 체]를 공부 후 적용해 보았습니다.

여기서 제가 생각했던것 중 어려운 부분은 [에라토스네스 체]의 구현보다도 True 값을 넣는 prime list에 있었다고 생각합니다.

True 값이 들어있는 list를 10개만 만들경우 n=10인 경우에는 통과할 수 있으나
n값 자체가 소수 중 하나인 5와 같은 경우는 개수에 포함되지 않아 정답보다 하나 부족한 2개가
출력이 됩니다.😂

전체적은 알고리즘의 틀을 만들고 True값을 설정하는 부분에서 많은 시간을 보냈습니다.

💪성장통으로 생각하겠습니다.

=============================================================

def solution(n):
    prime = [True] * (n+1)
    sqrt = int(n**0.5)
    for i in range(2, sqrt+1):
        if prime[i] == True:
            for j in range(i+i, n+1, i):
                prime[j] = False    
    return len([i for i in range(2,n+1) if prime[i] == True])