c语言穷举法函数 c语言穷举法求素数

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

c语言编程_穷举法求两个数的最大公约数

求最大公约数算法：

(1)辗转相除法

两整数a和b：

① a%b得余数c

② 若c=0，则b即为两数的最大公约数，结束

③ 若c≠0，则a=b，b=c，再回去执行①

(2)相减法

两整数a和b：

① 若ab，则a=a-b

② 若ab，则b=b-a

③ 若a=b，则a（或b）即为两数的最大公约数，结束

④ 若a≠b，则再回去执行①

(3)穷举法：

① i= a b中的小数

② 若a，b能同时被i整除，则i即为最大公约数，结束

③ i--，再回去执行②

C语言穷举法求最小公倍数

1、调整一下顺序：对两个正整数a,b,如果若干个a之和能被b所整除（或若干个b之和能被a所整除），则该和数即为所求的最小公倍数。

“若干个a之和”即a的若干倍，它就是a的倍数，如果“若干个a之和”能被b所整除，则它也是b的倍数，因此它就是a和b的最小公倍数。

同理“若干个b之和”也是一样的解释。

2、函数部分：因为“最小公倍数”必定比a,b两数中较小的数大，所以先找出两数其中较大的数给p，较小的数给q，并把较大的数存到temp（用于后面若干个较大数之和）。然后用较大数p除以较小数q，如果能整除，则p就是最小公倍数；如果不能整除，则给p再加上较大数（即若干个较大数之和），再次除以q判断是否能整除，如此循环直到能整除为止，此时的p（已经加了若干次较大数）即为a,b的最小公倍数。

穷举法用C语言怎么写？

共有156种方案：

#includestdio.h

int main()

{ int a,b,c,n=0;

for(a=1; a27; a++)

for(b=a+1; b(800-30*a)/20; b++)

{ c=(800-30*a-20*b)/10;

if(a*30+b*20+c*10==800 bc)

{ n++;

printf("%2d %2d %2d\t",a,b,c);

}

printf("\nTotal=%d\n",n);

return 0;

}