'Discrete Math/Number theory'에 해당되는 글 3건

  1. 2011.10.06 Euclidean algorithm (유클리드 호제법)
  2. 2011.10.06 소수판별법
  3. 2011.10.05 Sieve of Erathosthenes(에라토스테네스의 체) (2)

두 자연수 a,b 의 GCD(Great Common Divisor)인 d를 기호로 (a,b)로 나타내면 d=(a,b)이다.
a,b는 모두 GCD인 d로 나누어 떨어지므로 a-b도 d로 나누어 떨어진다.
※ d는 a-b와 b의 GCD이다.
 이와 같은 과정을 반복하여 두 수의 GCD를 구하는 방법이 Euclidean algorithm!! 


#include <iostream>
using namespace std;
int main(void)
{
int i,j,GCD;
cout << "Input the 1st number : ";
cin >> i;
cout << "\nInput the 2nd number : ";
cin >> j;
while(1)
{
if(i==j)
{
GCD = i;
cout << "\n\n GCD : " << GCD << endl;
break;
}

if(i>j)
i=i-j;
else
j=j-i;
}
}


 

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

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

더보기

 

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

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


그리스의 수학자이인 에라토스테네스가 고안한 소수를 찾는 방법으로 특정 양의 정수보다 작은 소수를 찾아내는 방법이다.

자연수 n보다 작은 소수 p를 구하는 방법.
How to)
1. 1을 지우고 p를 2로 놓는다.
2. p를 남기고 n보다 작은 p의 배수를 모두 제거한다.
3. 아직 제거되지 않은 p보다 큰 수 중에서 최소의 수를 다시 p로 놓는다.
4. 다시 2. 로 돌아간다.


프로그래밍 구현 예)
 
#include <iostream>
using namespace std;
int main(void)
{
int i;
            cout << "Input the number : ";                       
            cin >> i;
            while(i)
            {
                        for(j=2;j<=i;j++)
                        {
                                    if(i%j == 0 && i!=j)
                                                break;
                                    if(i==j)
                                    {
                                                cout << "We've found : ";
                                                cout << i << endl;
                                                return 0;
                                    }
                        }
            i++;
            };
}


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

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

티스토리 툴바