[프로그래머스 Level 1 / Python3] - 소수 찾기

문제 설명

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를 반환

 

문제 링크: https://programmers.co.kr/learn/courses/30/lessons/12921

프로그래머스

---

문제 풀이

에라토스테네스의 체 방법 활용 

1부터 n까지의 수 중에서 소수의 배수는 모두 걸러내는 방법

반복문은 2부터 시작하여 최대 약수인 n의 제곱근까지 돈다.

# 에라토스테네스의 체 활용
def solution(n):        
    answer = [False, False] + [True]*(n-1)    # 1은 소수가 아니므로 제외한 나머지 True로 초기화 (맨 앞은 인덱스 맞추기)
    max = int(n**0.5)                         # 최대 약수는 n의 제곱근
    
    for i in range(2, max+1):
        if answer[i] == True:                 # 소수일 때
            for j in range(i*2, n+1, i):      # 그 배수들을 모두 검사하여 False로 변환
                answer[j] = False     
    
    return answer.count(True)