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

{{문제}}

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

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

 

※제한 조건※

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

---

{{풀이}}

def solution(n):
    l = list(filter(lambda x: x%2!=0, range(1, n+1))) #짝수 거르기
    cnt = 0
    result = 0
    for j in l:
        for i in range(1, n+1):
            if j%i == 0: 
                cnt +=1
        #print(j,'-',cnt) [1,n] 각각의 홀수가 갖는 약수의 개수 
        if cnt == 2: 
            result += 1
        cnt = 0 
    return result+1 #짝수 중에는 소수가 2뿐이므로, +1

**시간초과가 걸려서 아직 고민중이에요...