더보기

 

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

대우명제를 부정 -> 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;

}



 

'Discrete Math > Number theory' 카테고리의 다른 글

Euclidean algorithm (유클리드 호제법)  (0) 2011.10.06
소수판별법  (0) 2011.10.06
Sieve of Erathosthenes(에라토스테네스의 체)  (2) 2011.10.05
Posted by 퍼덕퍼덕