Programmers - Lv1 - 소수 찾기

소수 찾기

문제설명

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

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

python code - 효울성 테스트 미통과

def solution(n):
    answer = 1
    if n == 2:
        return answer
    else:
        for i in range(3, n + 1, 2):
            prime = True
            for j in range(2, i):
                if i % j == 0:
                    prime = False

            if prime:
                answer += 1

    return answer

문제풀이

• for문을 통하여 일일히 검사하는 것은 효율성을 떨어트린다.
• 집합연산을 통하여 특정 수의 배수를 제거한다.

python code

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