Lv1. 소수 찾기

문제 보기 :  소수 찾기

프로그래머스

 

---

문제

• 정답률 : 62%

---

작성 코드

def solution(n):
    answer = 0
    lst = [False, False, True]+[True]*(n-2) 
    
    for i in range(2,n+1):
        if lst[i]: 
            answer += 1
            for jj in range(2,(n//i)+1):
                lst[i*jj]=False 
    return answer

---

풀이

전에 아리.. 누구의 체를 본 것 같은데, 이 알고리즘이 딱 적절하다고 생각해서 사용했다. 

True, False 리스트의 index를 사용해서 True인 index가 나타날 때, answer += 1을 수행하고
리스트 내 index의 배수들은 모두 False로 처리한다. 

이렇게 하면, 효율성에서 시간 초과도 안나고 아주 빠르게 처리할 수 있다