소수 판별 알고리즘 (1) 썸네일형 리스트형 기본적인 소수 판별 알고리즘 2가지 소수가 자기 자신과 1만을 약수로 가진다는 것은 널리 알려진 사실이다. 알고리즘 문제를 풀 때 어떤 수가 소수인지 아닌지 판별할 상황이 오는데 그 수가 너무 크지만 않다면 게시글에서 알려줄 두가지 방법을 이용하여 적절히 해결할 수 있다. 판별법 1. 완전 탐색을 통한 검사 자연수 N이 소수인지 아닌지 판별하는 가장 간단한 방법은 2부터 $\sqrt[]{N}$ 까지 나눠보면서 나눠지는지 아닌지 확인하는 것이다. 왜 모든 수를 나눠보는게 아니라 제곱근으로도 충분할까? N이 합성수라고 한다면 N은 $N = ab = ba$처럼 두 자연수 a, b의 곱으로 나타낼 수 있다. 이 때 a와 b는 $2 \leq a \leq \sqrt[]{N}, \; \sqrt[]{N} \leq b \leq \frac{N}{2}$ 또는.. 이전 1 다음