Lv1. 소수 찾기

# 문제 설명

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

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

# 제한 사항

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

# 입출력 예

입출력 예 설명

입출력 예 #1 1부터 10 사이의 소수는 [2,3,5,7] 4개가 존재하므로 4를 반환

입출력 예 #2 1부터 5 사이의 소수는 [2,3,5] 3개가 존재하므로 3를 반환

문제 해결 시 고려사항

• 에라토스테네스의 체 활용

본 문제는 1부터 주어지는 n까지의 수 중 소수의 개수를 반환하는 문제이다. 소수를 찾기 위해 대표적으로 활용되는 에라토스테네스의 체를 활용하여 문제를 해결한다.

소수의 기본적인 특성은 약수가 자기 자신과 1밖에 없는 수이다. 따라서 2를 제외한 짝수는 소수가 될 수 없다. 이에 기반하여 문제를 푼다.

우선 2를 제외하고 홀수에 대한 n까지의 set를 생성한다.

 # 3부터 n까지 2씩 증가시킨 set을 만듦
 a = set([i for i in range(3,n+1,2)])

이 후 3부터 n까지의 수들에 대한 탐색을 진행한다. 이 탐색을 진행할 땐 탐색 중인 수 i가 a 내에 존재하면 그 수의 배수들을(2배수 이상) 모두 a에서 제거시킨다. 이 이유는 앞서 설명한 소수의 특성 때문이다. 1과 자기 자신밖에 약수가 존재할 수 없기 때문에 그의 배수들은 자연스럽게 소수에서 제외되기 때문이다.

 # 3~n 까지 2씩 증가시키며 탐색
     for i in range(3,n+1,2):
         # i가 a 내에 존재하면
         if i in a:
             # 해당 수의 i의 2배수부터 n이하의 배수들을 a에서 제거
             a-=set([i for i in range(i*2,n+1,i)])

여기까지의 과정을 거치면 1~n까지의 소수를 찾을 수 있다. 하지만 3부터 탐색을 진행하였기 때문에 2를 포함한 개수를 반환하여 주면 문제를 해결할 수 있다.

 # 2를 포함한 개수 출력
     return len(a)+1

전체 코드

def solution(n):
    # 3부터 n까지 2씩 증가시킨 set을 만듦
    a = set([i for i in range(3,n+1,2)])
    # 3~n 까지 2씩 증가시키며 탐색
    for i in range(3,n+1,2):
        # i가 a 내에 존재하면
        if i in a:
            # 해당 수의 i의 2배수부터 n이하의 배수들을 a에서 제거
            a-=set([i for i in range(i*2,n+1,i)])
    # 2를 포함한 개수 출력
    return len(a)+1