프로그래머스 리뷰3 소수찾기

처음 접근

def solution(n):
    list = []
    count = 0
    # 1은 제외니까
    for i in range(2, n+1):
        for j in range(1, i+1):
            if i % j == 0:
                count += 1
        list.append(count)
        count = 0
    
    return(list.count(2))
    

n을 5라고 치면 1을 제외하고
5를 2345로 나눴을때
나머지가 0인 것이 2개이면 소수라는 것에 포커스를 두고 짠 코드인데...

상당히 비효율 적인 접근 이었나 보다..
생각해보면 n이 커질수록 시간복잡도가 상당히 커지는걸 생각을 내가 못한것 같다.

에라토스테네스의 체

고대 그리스에 살던 에라토스테네스는 대체 어떻게 이걸 생각해낸걸까 이거 생각해내는데 얼마나 걸렸을까
아 .
알고리즘[편집]
1.2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다.
2는 소수이므로 2를 쓴다.
자기 자신을 제외한 2의 배수를 모두 지운다.
남아있는 수 가운데 3은 소수이므로 3을 쓴다.
자기 자신을 제외한 3의 배수를 모두 지운다.
남아있는 수 가운데 5는 소수이므로 5를 쓴다.
자기 자신을 제외한 5의 배수를 모두 지운다.
남아있는 수 가운데 7은 소수이므로 7을 쓴다.
자기 자신을 제외한 7의 배수를 모두 지운다.
위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다.

def solution(n):
    num=set(range(2,n+1)) # 2부터 n+1까지의 집합

    for i in range(2,n+1): # 2부터 n까지 반복문
        if i in num: # 만약 i가 num 집합에 있다면
            num-=set(range(2*i,n+1,i)) # i의 배수는 num 집합에서 제외
    return len(num) # num에 남아있는 숫자의 개수가 소수의 개수

속상하다. 분발하자