[파이썬 프로그래머스] 소수 찾기

❓ 문제

---

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

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

>  제한 조건

---

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

✔️ 풀이

---

sosu = [0]*2 + [1 for _ in range(999999)]
for num in range(2, len(sosu)):
    if sosu[num]:
        for i in range(num*2, len(sosu), num):
            sosu[i] = 0

def solution(n):
    return sosu[:n+1].count(1)

Notice: 이 게시물은 programmers.co.kr 사이트를 참고하였습니다.