프로그래머스. 소수 찾기 파이썬 풀이

프로그래머스. 연습문제. Level 1. 소수 찾기 파이썬 풀이

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

범위 소수 찾기 알고리즘 에라토스테네스의 체 참고 https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

import math

# 소수 판별
def is_prime_number(n):
    # 처음엔 모든 수가 소수(True)인 것으로 초기화한다 (0과 1은 제외)
    array = [True for i in range(n+1)]
    
    # 에라토스테네스의 체
    for i in range(2, int(math.sqrt(n)) + 1): # 2부터 n의 제곱근까지의 모든 수를 확인하며
        if array[i] == True: # i가 소수인 경우
            # i를 제외한 i의 모든 배수를 지우기
            j = 2
            while i*j <= n:
                array[i*j] = False
                j += 1
    
    return [ i for i in range(2, n+1) if array[i]]
            
           
def solution(n):
  
    return len(is_prime_number(n))