[알고리즘] Programmers 소수 찾기 #Python

[[Programmers] 소수 찾기

바로가기](https://school.programmers.co.kr/learn/courses/30/lessons/12921)

📍 문제 설명

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

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

---

📍 제한 사항

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

---

📍 입출력 예

n	result
10	4
5	3

---

📍 입출력 예 설명

입출력 예 #1
1부터 10 사이의 소수는 [2,3,5,7] 4개가 존재하므로 4를 반환

입출력 예 #2
1부터 5 사이의 소수는 [2,3,5] 3개가 존재하므로 3를 반환

---

📍 풀이

• 에라토스테네스의 체 알고리즘을 이용하여 n 이하의 숫자에 존재하는 소수의 개수를 구한다.
• 2 ~ n 까지의 수 중에서 2 부터 입력받은 숫자 n 의 제곱근의 값 이하의 정수의 배수의 값을 모두 지우면 남은 값들은 모두 소수이다.

✍ 코드

def solution(n):
    answer = 0
    lst = [0, 0] + [1] * (n-1)
    for i in range(2,int(n**(1/2))+1):
        for j in range(2,n//i+1):
            lst[i*j] = 0
    return lst.count(1)