[파이썬/python] 프로그래머스 : 소수 찾기 (Lv.1) (에라토스테네스의 체)

def solution(n):
    def prime(x):
        for j in range(2,int(x**0.5)+1):
            if x % j == 0 :
                return False
        return True
    
    cnt = 0
    for i in range(2,n+1):
        if prime(i):
            cnt += 1
    return cnt

효율성이 별로다

 

 

 

다른사람풀이 (에라토스테네스의 체)

def solution(n):
    num=set(range(2,n+1))

    for i in range(2,n+1):
        if i in num:
            num-=set(range(2*i,n+1,i))
    return len(num)

n = 10이면

1. num=set(range(2,n+1)) => {2,3,4,5,6,7,8,9,10}

2. i가 num안에 있으면 i의 배수 모두 지워줌 

3. num의 길이 출력

 

 

def solution(n):
    num=set(range(2,n+1))

    for i in range(2,int(n**0.5)+1):
        if i in num:
            num-=set(range(2*i,n+1,i))
    return len(num)

범위를 int(n**0.5)+1 로 바꿔주니까 약간 더 빨라졌다