코딩테스트 연습>연습문제>소수 찾기

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

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

제한 조건
n은 2이상 1000000이하의 자연수입니다.
입출력 예
n result
10 4
5 3
입출력 예 설명
입출력 예 #1
1부터 10 사이의 소수는 [2,3,5,7] 4개가 존재하므로 4를 반환

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

위 문제는 범위 내의 소수의 개수를 구하는 문제로 에라스토테네스의 체를 이용하여 풀 수 있다.
에라스토테네스의 체란 에라토스테네스가 고안한 소수를 찾는 방법으로, 이 방법으로 소수를 찾으려면 2부터 시작해 자연수를 차례로 쓴 다음, 2 이외의 2의 배수, 3 이외의 3의 배수, 5 이외의 5의 배수의 순서로 수를 지워나가 끝에 남는 수가 소수이다.

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

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

    return len(answer)
    

1. answer 에 set()자료형으로 2~n까지의 정수를 저장한다.

2. 2 ~ n까지 for 문을 돌리며 answer에 i 가 있다면 n까지의 수 중 i의 배수를 모두 제거한다.

3. answer에는 2~n까지의 소수만 남아있게 된다.

4. len(answer)을 반환하면 해결!

2021.01.30 복습 완

처음에 에..어쩌고의 체를 쓰려고 구성했던게 n % i == 0 을 이용하서 하려고 했는데 실패함