最大公約数のユークリッド、連続正整数検出、公共質量因数の3種類の解法と分析

/*
*******************    **********************************

*    ：GREATEST_COMMON_DIVISION.cpp
*     ：       m，n      
*       ：                                 。
*     ：      、        、        

*/

/*
**********    *************
*     ：GcdEuclid(int m, int n)
*     ：m、n        
*      ：  m n      

*     ：      ：
	   ：  n=0，  m      ，  ；       
	   ： n  m，      r；
	   ： n     m， r     n，     。
*     ：
	    ：GcdEuclidRecursion(m,n)
	     ：GcdEuclid(m,n)
*      ：
	          ，      gcd  ，             （            ）
	        	O(lgn)
*/

#include 
#include "greatest_common_division.h"  
#include "primality_check.h"
#include 
using namespace std;

//     
int GcdEuclidRecursion(int m, int n)
{
	return (!n ? m : GcdEuclidRecursion(n, m % n));  //   n   0，  0，     ，    
}
//      
int GcdEuclid(int m, int n)
{
	int r;
	while (n)
	{
		r = m % n;
		m = n;
		n = r;
	}
	return m;
}

/*
**********    *************
*     ：GcdContinuousIntegerTest(int m, int n)
*     ：m、n        
*      ：  m n      

*     ：       
	   ： min{m,n}    t
	   ：m  t，     0，      ；  ，     ；
	   ：n  t，     0，   t     ；  ，     ；
	   ： t   1，     。
*     ：
	
	     ：gcd_continuous_integer_test(m,n)
*      ：
	            1，    t-1 ，          
	        	O(n) = n/2
*/

int GcdContinuousIntegerTest(int m, int n)
{
	int temp = std::min(m, n);
	while (m % temp || n % temp)  //            ，               0          。      
	{
		temp -= 1;
	}
	return temp;
}

/*
**********    *************
*     ：GcdCommonPrimeFactors(int m, int n)
*     ：m、n        
*      ：  m n      

*     ：        
	   ：  m      ；
	   ：  n      ；
	   ：                          ；
	   ：            ，               。

*     ：

	     ：GcdCommonPrimeFactors(m,n)
*      ：
	O(n*(logn)^3)
	
*/
int GcdCommonPrimeFactors(int m, int n)
{
	int result = 1;

	std::vector prime_m, prime_n;

	//  m       
	//   m   ，m = 1 * m
	if (MilleRabin(m))
		prime_m.push_back(m);
	else
	{
		for (int temp = m, prime = 2; temp > 1; )
		{
			if (temp % prime)  //   prime  temp   ，prime + 1
				prime += 1;

			else if (MilleRabin(prime))
			{
				temp = temp / prime;  //   prime temp   ，  temp
				prime_m.push_back(prime);  //   prime   ，        
			}
			else
				prime += 1;  //            ，  prime
		}
	}

	//  n       
	//   n   ，n = 1 * n
	if (MilleRabin(n))
		prime_n.push_back(n);
	else
	{
		for (int temp = n, prime = 2; temp > 1; )
		{
			if (temp % prime)  //   prime  temp   ，prime + 1
				prime += 1;

			else if (MilleRabin(prime))
			{
				temp = temp / prime;  //   prime temp   ，  temp
				prime_n.push_back(prime);  //   prime   ，        
			}
			else
				prime += 1;  //            ，  prime
		}
	}

	while (!prime_m.empty() && !prime_n.empty())
	{
		if (prime_m[0] == prime_n[0])
		{
			result = result * prime_m[0];//     ，  
			prime_m.erase(prime_m.begin());  //   
			prime_n.erase(prime_n.begin());
		}
		else if (prime_m[0] < prime_n[0])  //         
		{
			prime_m.erase(prime_m.begin());  
		}
		else
			prime_n.erase(prime_n.begin());
	}
	

	
	
	return result;
}