[python] 1. 소수 찾기(feat. 에라토스테네스의 체)

문제 설명

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

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

 

제한 조건

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

 

입출력 예

n	result
10	4
5	3

 

---

연습장

1. 2이상 n이하의 자연수 생성한다.

2. 그 자연수가 소수인지 아닌지 판별한다.

3. 소수라면 result에 1을 더한다.

4. 효율성을 위해 에라토스테네스의 체를 적용한다.

 (2의 배수라면 소수가 아닌 것이기 때문에 range(3, n+1, 2)를 적용)

 

에라토스테네스의 체 ★

ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전

에라토스테네스가 고안한 소수를 찾는 방법으로, 이 방법으로 소수를 찾으려면 2부터 시작해 자연수를 차례로 쓴 다음, 2 이외의 2의 배수, 3 이외의 3의 배수, 5 이외의 5의 배수의 순서로 수를 지워나가 끝에 남는 수가 소수이다.

 

나의 코드

def solution(n):
    result = 0
    if n == 2:
        return 1
    else: 
        for x in range(3, n+1, 2):
            a = 0
            for y in range(3, int(x**0.5)+1):
                if x % y == 0:
                    a += 1
                    break
            if a == 0:
                result += 1
    return result+1

다른 사람들이 한거랑 비교해보니 너무 지저분하다;;;

 

모범 답안

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)