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

프로그래머스

Lv.1 [1차] 소수 찾기

1.문제

input 정수 n
output 2~n 사이 소수찾기

2. 풀이

for문으로 비교
-> runtime error

3. 코드

나의 코드

def solution(n):
    answer = n-1
    for i in range(2,n+1):
        for j in range (2, i):
            if i % j == 0:
                answer -= 1
                break
    return answer

모범코드

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)

에라토스테네스의 체
2부터 자연수를 차례로 쓴 다음, 2 이외의 2의 배수, 3 이외의 3의 배수, 5 이외의 5의 배수의 순서로 수를 지워나가 끝에 남는 수가 소수