《算法设计与分析基础》三种求最贵族约数的方法C++实现-欧几里德辗转相除、连续整数检测、质因数相乘

《算法设计与分析基础》三种求最大公约数的方法C++实现--欧几里德辗转相除、连续整数检测、质因数相乘

#include <iostream>
#include <cmath>
using namespace std;
int gcd_1(int x,int y);
int gcd_2(int x,int y);
int gcd_3(int x,int y);
int Sieve(int n);
int *prime;//存放质数的数组指针
int main()
{
	int a=0,b=0;
	cin>>a>>b;
	cout<<"欧几里德辗转相除法："<<gcd_1(a,b)<<endl;
	cout<<"连续整数检测法    ："<<gcd_2(a,b)<<endl;
	cout<<"小学方法          ："<<gcd_3(a,b)<<endl;
	/*int s=Sieve(200);
	for(int k=0;k<s;k++)
        cout<<prime[k]<<" "<<endl;
	return 0;*/
}


//函数描述：欧几里德辗转相除法求最大公约数
//参数：两个大于等于0的整数
//返回值：这两个数的最大公约数,若返回-1表示出错
int gcd_1(int x,int y)
{
    if(x>=0&&y>=0)
    {
        return (y==0)?x:gcd_1(y,x%y);
    }
    else
    {
        return -1;
    }
}


//函数描述：连续整数检测法求最大公约数
//参数：两个大于等于0的整数
//返回值：这两个数的最大公约数,若返回-1表示出错
int gcd_2(int x,int y)
{
    if(x>0&&y>0)
    {
        int t=(x<y)?x:y;
        while(t>0)
        {
            if(x%t==0)
            {
                if(y%t==0)
                {
                    return t;
                }
            }
            t--;
        }
    }
    else
    {
        return -1;
    }
}

int gcd_3(int x,int y)
{

    if(x>0&&y>0)
    {
        int result=1;//存放最大公约数
        int min=(x<y)?x:y;
        int num=Sieve(min);
        if(num>0)
        {
            int i=0;//用来标记prime[]的下标
            while((i<num)&&(x/prime[i]>=1)&&(y/prime[i]>=1))
            {
                //如果同时是这两个质数的质因数，那就让result*=prime[i];
                if((x%prime[i]==0)&&(y%prime[i]==0))
                {
                    result*=prime[i];
                    x/=prime[i];
                    y/=prime[i];
                }
                else
                {
                    i++;
                }
            }
        }
        return result;
    }
    else
    {
        return -1;
    }


}

//函数描述：计算所有小于等于n的质数，存放在全局的prime[]中
//参数：int类型的数n，为计算的上限
//返回值：所有小于等于n的质数的个数
int Sieve(int n)
{
    //全部初始化为0
    int *tmp=new int[n+1]();
    for(int i=0;i<n+1;i++)
        tmp[i]=0;
    //我在自己电脑上不用上面的语句也能清零，学校实验室不行，why
    //这里出现一个问题：我如果直接传进来常数eg Sieve(200) 可以初始化为全0
    //但是如果用一个变量传进来，就不会初始化为全0 why？
    //for(int p=0;p<n+1;p++)
    //    cout<<tmp[p]<<endl;
    for(int i=2;i<sqrt(n+1);i++)
    {
        //没被消去
        if(0==tmp[i])
        {
            int j=i*i;
            while(j<=n+1)
            {
                tmp[j]=1;//1表示消去
                j+=i;
            }
        }
    }

    //现在所有小于等于n的质数全部存在tmp[]数组中
    //如果tmp[i]为0则，i是质数
    prime=new int[n+1];
    int i=0;
    int sum=0;//用来记录质数的个数
    for(int j=2;j<=n+1;j++)
    {
        //如果是质数，则复制到prime中
        if(0==tmp[j])
        {
            sum++;
            prime[i++]=j;
        }
    }
    return sum;
}

我的新浪博客地址：http://blog.sina.com.cn/s/blog_64ecfc2f0101atrl.html