算法程序——C语言之函数调用（17）
//函数调用
==========================================================
题目：求4个数的最大公约数和最小公倍数。
==========================================================
#include&stdio.h&
long gys(long m,long n)
{t=m;m=n;n=t;}
while((r=m%n)!=0)
return (n);
long gys(long a,long b,long c)
q=gys(gys(a,b),c);
return(q);
long gys(long a,long b, long c,long d)
q=gys(gys(a,b,c),d);
return (q);
long gbs(long a,long b)
return a*b/gys(a,b);
long gbs(long a,long b,long c)
return gbs(a,b)*c/gys(gbs(a,b),c);
long gbs(long a,long b,long c,long d)
return gbs(a,b,c)*d/gys(gbs(a,b,c),d);
void main()
long a,b,c,d;
long gyshu,
printf(&输入四个数：&);
scanf(&%ld%ld%ld%ld&,&a,&b,&c,&d);
gyshu=gys(a,b,c,d);
gbshu=gbs(a,b,c,d);
printf(&%ld、%ld、%ld、%ld 的最大公约数是：%ld\n&,a,b,c,d,gyshu);
printf(&%ld、%ld、%ld、%ld 的最小公倍数是：%ld\n&,a,b,c,d,gbshu);
====================================================================
要点在于重复调用！始终把计算结果作为一个数，就实现了先计算两个数a,b,
将gys(a,b)或gbs(a,b)作为一个数与c重新调用函数“gys”或“gbs”，同理，
将gys(a,b,c)或gbs(a,b,c)作为一个数与重新调用函数“gys”或“gbs”，
甚至可以实现更多数字的公约数和公倍数！如果数字比较多，而且大，就需要
改为double型！
缺点：显然这种方法写程序虽然直观但是很慢！读者可以试着用一个temp变量
保存最新的公约数，直到最后一个公约数求完为之。则问题转化为始终求两个
数的公约数。
=====================================================================
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：42939次
积分：1473
积分：1473
排名：第19309名
原创：103篇
评论：13条数论（16）
今天做题遇见，于是就搜了一下，于是就有了这篇文章。（其实我不知道原理....Orz）我觉得分解质因数的最优算法应该不是我这篇文章中的这个.....谁有好的算法可以给我说一下，谢谢。
1.有多少个约数：
先分解质因数
因数的次数分别是4,2,1
所以约数的个数为(4+1)*(2+1)*(1+1)=5*3*2=30个
先分解质因数
720=24*32*51
因数的次数分别是4,2,1
所以约数的个数为(4+1)*(2+1)*(1+1)=5*3*2=30个
2.所有约数之和：
2004的约数之和为:1,&2,&3,&4,&6,&12,&167,&334,&501,&668,&&&=&4704
如何求一个数所有约数之和呢?
首先,应用算术基本定理,化简为素数方幂的乘积。
X&=&a1^k1&*&a2^k2........an^kn
X的所有素数之和可用公式(1+a1&+&a1^2...a1^k1)&*&(1+a2&+&a2^2...a2^k2)&*&.....(1+an&+&an^2...an^kn)表示
2004&=&2^2&&*&3&&*167
２００４所有因子之和为(1&&+&2&+&2^2)&*&(1&+&3)&*&(&1&+&167)&=&4704;
程序实现的时候，可利用等比数列快速求1&+&a1&+&a1^2&+&.....a1^n;
3.分解质因数
我用的算法是这个：
程序分析：对n进行分解质因数，应先找到一个最小的质数k，然后按下述步骤完成：&&&
(1)如果这个质数恰等于n，则说明分解质因数的过程已经结束，打印出即可。&
(2)如果n&&&&k，但n能被k整除，则应打印出k的值，并用n除以k的商,作为新的正整数你n,&
　重复执行第一步。&
(3)如果n不能被k整除，则用k+1作为k的值,重复执行第一步。&
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：42251次
积分：1439
积分：1439
排名：第19864名
原创：98篇
转载：54篇
(3)(1)(6)(1)(1)(1)(4)(1)(21)(7)(21)(16)(23)(4)(25)(2)(3)(12)一个数的约数和倍数的求法_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
一个数的约数和倍数的求法
上传于||暂无简介
阅读已结束，如果下载本文需要使用1下载券
想免费下载本文？
你可能喜欢质因数分解（给定一个整数，求该数的所有质因数）
题目：质因数分解，给定一个整数，求该数的所有质因数，例如 90 = 2*3**3*5。
　　首先，质数的定义（引用百度百科）：
　　质数又称素数，有无限个。一个大于1的自然数，如果除了1和它自身外，不能被其他自然数整除（除0以外）的数称之为素数（质数）；否则称为合数。根据算术基本定理，每一个比1大的整数，要么本身是一个质数，要么可以写成一系列质数的乘积；而且如果不考虑这些质数在乘积中的顺序，那么写出来的形式是唯一的。
　　在自然数域内，质数是不可再分的数，是组成一切自然数的基本元素。 比如，10 是由两个 2 和两个 3 组成的，正如水分子是由两个 H 原子和一个 O 原子组成的一样。只是和化学世界不同，质数有无穷多个，因此算术世界的元素也就有无穷多个。算术世界内的一切对象、定理和方法，都是由其基本元素质数组成的。
　　所以，注意，最小的质数（素数是2），1既不是质数也不是合数。回到题目，求一个整数的所有质因数，我们举几个例子来分析问题。比如，数字9 = 3*3，再比如18 = 2*9 = 2*3*3。所以，求解的过程就是从i等于整数2开始搜索，看是否能整除n，如果n能够被一个素数整除，那么判断n/i的商是不是素数，如果不是素数，那么继续求商的所有质因数；如果商也是素数，那么所有的质因数都被找出来了，停止递归。
　　下面贴代码，首先是判断一个数是不是素数的函数：
&1 bool isZS(int n)
&3 & & int sqrtN = (double)sqrt((double)n);
&4 & & if ( n==1 )
&5 & & if ( n==2 )
&6 & & if (sqrtN*sqrtN == n)
&7 & & for (int i=2;i&=sqrtN;i++)
&9 & & & & if ((n%i) == 0 )
10 & & & & & &
　　然后是递归求解所有的质因数：
&1 void findAllZYS(int n)
&3 & & if (n == 1)&
&5 & & & & cout&&1;
&6 & & & &
&8 & & if (n == 2)&
10 & & & & cout&&2;
11 & & & &
13 & & if (isZS(n))
15 & & & & cout&&& &&&n&&
16 & & & &
18 & & int i = 2;
19 & & for (i=2;i&=n;i++)
21 & & & & if (isZS(i) && n%i == 0)
22 & & & & {
23 & & & & & & cout&&i&&& &&&
24 & & & & & &
25 & & & & }
28 & & int nxtN = n /
29 & & if (isZS(nxtN))
31 & & & & cout&&nxtN&&& &&&
32 & & & &
34 & & else
36 & & & & findAllZYS(nxtN);
(window.slotbydup=window.slotbydup || []).push({
id: '2467140',
container: s,
size: '1000,90',
display: 'inlay-fix'
(window.slotbydup=window.slotbydup || []).push({
id: '2467141',
container: s,
size: '1000,90',
display: 'inlay-fix'
(window.slotbydup=window.slotbydup || []).push({
id: '2467143',
container: s,
size: '1000,90',
display: 'inlay-fix'
(window.slotbydup=window.slotbydup || []).push({
id: '2467148',
container: s,
size: '1000,90',
display: 'inlay-fix'君，已阅读到文档的结尾了呢~~
扫扫二维码，随身浏览文档
手机或平板扫扫即可继续访问
ACM知识：求一个数有多少约数及所有约数之和、分解质因数
举报该文档为侵权文档。
举报该文档含有违规或不良信息。
反馈该文档无法正常浏览。
举报该文档为重复文档。
推荐理由：
将文档分享至：
分享完整地址
文档地址：
粘贴到BBS或博客
flash地址：
支持嵌入FLASH地址的网站使用
html代码：
&embed src='/DocinViewer-4.swf' width='100%' height='600' type=application/x-shockwave-flash ALLOWFULLSCREEN='true' ALLOWSCRIPTACCESS='always'&&/embed&
450px*300px480px*400px650px*490px
支持嵌入HTML代码的网站使用
您的内容已经提交成功
您所提交的内容需要审核后才能发布，请您等待！
3秒自动关闭窗口