求两个数的公约数有多少个

题目描述：

给定两个正整数a，b（1<=a,b<=100000000）,计算他们公约数的个数。
如给定正整数8和16，他们的公约数有：1、2、4、8，所以输出为4。

输入：

输入包含多组测试数据，每组测试数据一行，包含两个整数a，b。

输出：

对于每组测试数据，输出为一个整数，表示a和b的公约数个数。

样例输入：

8 16
22 16

样例输出：

4 

2

这题并不难，关键是它卡时间。所以要优化一下

辗转相除法又名欧几里得算法

两个整数的最大公约数是能够同时整除它们的最大的正整数。辗转相除法基于如下原理：两个整数的最大公约数等于其中较小的数和两数的相除余数的最大公约数。例如，252和105的最大公约数是21（252 = 21 × 12；105 = 21 × 5）；因为252 / 105 = 2余42，所以105和42的最大公约数也是21。在这个过程中，较大的数缩小了，所以继续进行同样的计算可以不断缩小这两个数直至余数变为零。这时的除数就是所求的两个数的最大公约数

#include <cstdio>  
#include <iostream>  
using namespace std;  
int main()  
{  
    int a,b,temp;  
    int count,max,i;  
    while(~scanf("%d%d",&a,&b))  
    {  
        while(a%b!=0)  
        {  
            temp=a%b;  
            a=b;  
            b=temp;  
        }                  //辗转相除法求出最大公约数   
        max=b;  
        count=0;  
        if(max==1)  
        {  
            printf("1\n");  
            continue;  
        }  
        for(i=1;i<max;i++)  
        {  
            if(b%i==0)  
            {  
                count++;  
                max=b/i; //由于该题卡时间，此处同时找到两个约数，减少遍历范围  
                if(max!=i)     
                    count++;  
            }  
        }  
        printf("%d\n",count);  
    }   
    return 0;  
}  

求两个数的公约数有多少个,布布扣,bubuko.com

求两个数的公约数有多少个

原文：http://blog.csdn.net/caluu/article/details/20469401