소수판별법

1 보다 큰 자연수 n 에 대하여 √n 보다 작거나 같은 모든 소수가  n을 나누지 못하면 n은 소수이다.

 

대우와 귀류법을 통한 증명)

대우명제를 부정 -> n이 합성수이면 n은 √n보다 작거나 같은 약수를 갖지 않는다.
n=ab(ab는 양의정수이고 1이 아니다)
가정에 의하면 2 ≤ a ≤ b < n
a > √n, b > √n
a x b > √n x √n
n > n -> 여기서 모순이 발생한다.

따라서 n이 소수가 아니라면 n의 약수 중에서 √n보다 작거나 같은 소수가 존재한다.
그러므로 자연수 n이 √n 이하의 어떤 소수로도 나누어 떨어지지 않으면 n 은 소수이다.

#include <iostream>

#include <cmath>

using namespace std;

int main(void)

{

int N,i;

cout << "Input the number : ";

cin >> N;

for(i=2;i<=sqrt(N);i++)

{

if(N%i == 0)

{

cout << "It's not the prime number " << endl;

return 0;

}

}

cout << "It's the prime number " << endl;

}