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

출처:: programmers.co.kr/learn/courses/30/lessons/12921?language=python3

분류:: 에라토스테네스의 체 

 

1. 문제 이해 및 해결과정

 

2. 풀이방법

 1.에라토스테네스의 체 

import math
def solution(n):
    answer = 0
    arr=[ True for _ in range(n+1)]
    
    for i in range(2,int(math.sqrt(n))+1):
        if arr[i]: #소수인 경우
            j=2
            while i*j<=n:
                arr[i*j]=False
                j+=1
    for i in range(2,n+1):
        if arr[i]:
            answer+=1
    return answer

 

3. 오답원인

 

4. 알게된 점