[프로그래머스] 소수 찾기(python)

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

프로그래머스

📌 문제 설명

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을 반환

---

🗒 풀이

import math


def is_prime_number(x):
    for i in range(2, int(math.sqrt(x)) + 1):
        if x % i == 0:
            return False  # 소수가 아님
    return True  # 소수


def solution(n):
    answer = 0
    for i in range(2, n + 1):
        if is_prime_number(i):
            answer += 1
    return answer

에라토스테네스의 체를 이용한다. 에라토스테네스의 개념이 아직 부족하다면, 다음의 글을 읽고 오는 것을 추천한다.

에라토스테네스의 체 핵심은 제곱근을 이용하는 것이다. N의 제곱근까지만 검사를 해도 충분히 소수인지 합성수인지 판별할 수 있다는 것이 에라토스테네스의 체 근간이다.

 

math.sqrt() 함수를 이용하여 제곱근을 구해줬다. 이때 math.sqrt() 함수는 float를 반환하므로, int로 변형해준다.

어렵지 않은 코드이므로 충분히 이해될 것이라 믿는다.

---

🤔 후기

한동안 에라토스테네스를 이해하느라 애를 먹어서 그런가 어렵지 않게 풀 수 있었다.

만약 에라토스테네스의 체를 몰랐더라면, 예전 백준문제 풀 때처럼 2 이상 n 미만의 수 중 나누어 떨어지는 수가 존재하는지 확인했을 것이다.

코드 제출을 하고 보니 효율성 검사도 하던데, 아마 에라토스테네스의 체로 풀지 않았다면 효율성 검사에서 실패가 뜨지 않았을까 싶다.