소수판정법 썸네일형 리스트형 소수판별법 1 보다 큰 자연수 n 에 대하여 √n 보다 작거나 같은 모든 소수가 n을 나누지 못하면 n은 소수이다. 대우와 귀류법을 통한 증명) 대우명제를 부정 -> n이 합성수이면 n은 √n보다 작거나 같은 약수를 갖지 않는다. n=ab(ab는 양의정수이고 1이 아니다) 가정에 의하면 2 ≤ a ≤ b √n, b > √n a x b > √n x √n n > n -> 여기서 모순이 발생한다. 따라서 n이 소수가 아니라면 n의 약수 중에서 √n보다 작거나 같은 소수가 존재한다. 그러므로 자연수 n이 √n 이하의 어떤 소수로도 나누어 떨어지지 않으면 n 은 소수이다. #include #include using namespace std; int main(void) { int N,i; cout > N; fo.. 더보기 이전 1 다음