57일차. 소수 찾기

링크

https://school.programmers.co.kr/learn/courses/30/lessons/12921

프로그래머스

 

문제

문제 설명

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

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

제한 조건

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

 

정답

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

 

풀이과정

 

소수 찾기는 에라토스테네스의 체를 이용해서 풀 수 있습니다. 모든 수를 가진상태로 맨 앞의 수는 소수이고, 그 수에 배수를 한 수는 모두 제거합니다. 그러면 그 다음수는 앞의 수의 배수가 아니므로 소수이고, 또다시 그 수의 배수를 모두 제거합니다. 이렇게 반복해서 수를 제거하면 남은 수는 모두 소수라는것입니다.

먼저 2는 소수이고, 2의 배수인 짝수는 모두 제거한다. 

a = set(range(3, n+1, 2))

자 그리고, 저 a에대해 순회를 돌면서 제거가 가능하면...좋지만 방법을 모르기떄문에..! ㅠㅠ 3 이상의 모든 홀수를 순회돌면서 제거하는방법밖에 없네요..

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

자 그리고 가장 중요한점은 2가 소수이므로 마지막엔 2를 포함시켜줘야한다는 것입니다.

return len(a) + 1