Mathematics (1) 썸네일형 리스트형 소수 판정과 에라토스테네스의 체 소수(Prime number)의 정의 1과 자기 자신 으로만 나누어 떨어지는 자연수 소수 판정법 주어진 $n$이 소수인지 판정 1. $ 1 < k < n $ 인 $ \forall k \in \mathbb{N} $ 에 대하여 $n \ \text{mod} \ k = 0$ 인지 검사하는 방법이 있다. 최악의 경우 $O(n)$의 시간복잡도를 가진다. 2. 검사 대상을 $ 1 < k \le \sqrt{n} $ 인 $ \forall k \in \mathbb{N} $로 축소해볼 수 있다. $ \sqrt{n} $ 이하의 자연수만 검사해도 되는 이유는 $ \sqrt{n} \leq k \leq n$ 인 임의의 $ k \in \mathbb{N} $가 $n$의 약수일 때, $n/k$ 또한 $n$의 약수이다 $ \sqrt{n}.. 이전 1 다음