最大公约数测试.cpp

求最大公约数的三种算法

// 最大公约数测试.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
/* */
/* 求最大公约数Great Common Divisor的三种算法 */
/* 1、使用欧几里得算法 */
/* 2、使用连续整数检测算法 */
/* 3、使用中学时代的算法(使用埃拉托色尼筛) */
/* Author:lixiongwei */
/* Time:06/11/11 Sun. */
/* WIN XP+(TC/Win_TC/VC++6.0) */
/* */
/*****************************************************/
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#define MAX 5000
/******************函数原型声明***********************/
unsigned int my_gcd1(unsigned int m,unsigned int n);
unsigned int my_gcd2(unsigned int m,unsigned int n);
unsigned int my_gcd3(unsigned int m,unsigned int n);
int my_sieve(unsigned int n,unsigned int *L);

int _tmain(int argc, _TCHAR* argv[])
{
	unsigned int m,n;

	printf("Please enter two number: ");
	scanf("%u %u",&m,&n);
	printf("\nGreat Common Divisor: my_gcd1(%u,%u) = %u\n\n",m,n,my_gcd1(m,n));
	printf("Great Common Divisor: my_gcd2(%u,%u) = %u\n\n",m,n,my_gcd2(m,n));
	printf("Great Common Divisor: my_gcd3(%u,%u) = %u\n\n",m,n,my_gcd3(m,n));

	getch();
	return 0;
}

/*******使用欧几里得算法 函数:my_gcd1()定义部分*******/
/******基于定理gcd(a,b)=gcd(a,a mod b)*******/
unsigned int my_gcd1(unsigned int m,unsigned int n)
{
	unsigned int temp=m;
	unsigned int r;

	if(m < n) /* swap m,n*/
	{
		m = n;
		n = temp;
	}

	if(0 == m)
	{
		printf("You must enter one number much than zero!");
		getch();
		exit(1);/*abnormity*/
	}

	while(n != 0)
	{
		r = m % n;
		m = n;
		n = r;
	}

	return m;
}

/*****使用连续整数检测算法 函数:my_gcd2()定义部分*****/
unsigned int my_gcd2(unsigned int m,unsigned int n)
{
	unsigned int t;

	if( (0 == m)&&(0 == n) )
	{
		printf("You must enter one number much than zero!");
		getch();
		exit(1);/*abnormity*/
	}
	if(0 == m)
		return n;
	if(0 == n)
		return m;

	t = (m < n) ? m : n;
	while(1)
	{
		if( ((m % t) == 0)&&((n % t) == 0) )
			break;
		else
			--t;
	}

	return t;
}

/****使用中学时代的算法(使用埃拉托色尼筛) 函数:my_gcd3()定义部分****/
unsigned int my_gcd3(unsigned int m,unsigned int n)
{
	unsigned int ml[MAX];
	unsigned int nl[MAX];
	unsigned int mr[MAX];
	unsigned int nr[MAX];
	unsigned int t=1;
	int i,jm,jn,mi,ni;
	int zm=0,zn=0;

	if( (0 == m)&&(0 == n) )
	{
		printf("You must enter one number much than zero!");
		getch();
		exit(1);/*abnormity*/
	}
	if(0 == m)
		return n;
	if(0 == n)
		return m;

	for(i=0; i<MAX; ++i)
	{
		ml[i]=0;
		nl[i]=0;
		mr[i]=0;
		nr[i]=0;
	}

	mi=my_sieve(m,ml);
	ni=my_sieve(n,nl);

	i=0;jm=0;
	while(i < mi)
	{
		while(1)
		{
			if( (m%ml[i])==0 )
			{
				mr[jm]=ml[i];
				m=m/ml[i];
				++jm;
			}
			else
				break;
		}/*inside while end*/
		++i;
	}/*out while end*/

	i=0;jn=0;
	while(i < ni)
	{
		while(1)
		{
			if( (n%nl[i])==0 )
			{
				nr[jn]=nl[i];
				n=n/nl[i];
				++jn;
			}
			else
				break;
		}/*inside while end*/
		++i;
	}/*out while end*/

	for(zm=0,zn=0; (zm<jm)&&(zn<jn); )
	{
		if(mr[zm] < nr[zn])
			++zm;
		if(mr[zm] > nr[zn])
			++zn;
		if(mr[zm] == nr[zn])
		{ t=t*mr[zm]; zm++;zn++;}
	}

	return t;
}

/*******************埃拉托色尼筛函数定义部分************************/
int my_sieve(unsigned int n,unsigned int *L)
{
	int i;
	unsigned int p,j,A[MAX];

	for(p = 2; p <= n; ++p)
		A[p]=p;
	for(p = 2; p*p <= n; ++p)
	{
		if(A[p] != 0)
		{
			j = p*p;
			while(j <= n)
			{
				A[j]=0;
				j += p;
			}
		}/*end if*/
	}/*end for*/

	i = 0;
	for(p=2; p<=n; ++p)
	{
		if(A[p] != 0)
		{
			L[i]=A[p];
			++i;
		}
	}

	return i;
}