在C++程序中怎样求两个数公约数的个数?紧急~~~
假如一个个数字去试的话，前面小的数字还行，但是到后面的大数字就不行了，最大的数有2147483647。就是如20和30的话，公约数个数为4个。各位大神给点思路吧~~~
[解决办法]
int gongyueshu(unsigned int no1,unsigned int no2)
{
unsigned int temp;
if(no1 > no2)
{
temp = no1;
no1 = no2;
no2 = temp;
}
vector<int> vFactor;
unsigned int i=1, nTop = no1;
int nCount = 0;
while (i< nTop)
{
nTop = no1/i;
if (no1%nTop ==0 && no2%nTop == 0)
{
vFactor.push_back(nTop);
nCount++;
}
if (nTop != i && no1%i ==0 && no2%i == 0)
{
vFactor.push_back(i);
nCount++;
}
i++;
}
for(int i = 0;i < vFactor.size();i++)
{
cout << "公约数：" << vFactor[i] << endl; // 显示公约数
}
return nCount;
}
int main(int argc, char** argv)
{
cout << gongyueshu(2100000000 ,3100000000) << endl;
cout << gongyueshu(20 ,30) << endl;
double t; //计算运行时间的代码
clock_t time;
time=clock();
t=(double)time/CLK_TCK;
cout<<"time is "<<t<<" seconds "<<endl;
//cout << nCount << endl;
getchar();
return 0;
}
公约数：5
4
time is 0.607 seconds
