BOJ1929 - 소수 구하기

문제 바로가기

https://www.acmicpc.net/problem/1929

Solved.ac* 난이도

* Solved.ac는 백준 온라인 저지의 문제들에 난이도를 매겨주는 서비스입니다. 자세한 내용은 홈페이지를 참고해주세요.

 

---

본문

---

해설

https://github.com/return0927/CodingWrite-UP/blob/master/BOJ/1929/1929.py

 

소수 구하는 알고리즘만 간단히 설명하자면

def check_prime(n: int) -> bool:
    if n == 1:
        return False
    for i in range(2, int(n**.5 + .5) + 1):
        if n % i == 0:
            return False
    return True

이다.

주어진 수가 1인 경우에는 소수가 아니라고 판단한다 (이 부분에는 논란이 있을 수 있으나 다른 문제에서도 아닌걸로 처리되었다)

그리고 소수판별은 아주 조금만 생각을 해도 \(O(\sqrt{n})\)만에 처리할 수 있음을 알 수 있다. 왜냐하면 16를 예로 들자면 \(\sqrt{16}=4\)인데, 4으로 나누었을 때 그 몫이 4이고, 그 이후의 약수가 존재하려면 이미 그 전에 16에서 그 이후의 약수를 나눈 몫이 앞에 있었어야한다. 따라서 그 뒤는 자동으로 결정되기 때문에 검사할 필요가 없다.

 

range(2, int(n**.5 + .5) + 1)

그래서 검사할 범위를 보자면 뭔가 난해할 수도 있다. \(\sqrt{n} + 0.5\)에서 0.5를 더해준 이유는 int로 cast하면서 반올림을 하는 기법이다. 뒤로 한 개를 더 체크한다고 크게 시간적인 면에서 버거울 것이 없기 때문에 하나정도는 더 여유있게 체크해줘도 나쁘지 않다