C语言程序设计100例

C语言程序设计100例之（5）：分解质因数例5分解质因数题目描述将一个正整数分解质因数。例如：输入90,输出90=2*3*3*5。输入输入数据包含多行，每行是一个正整数n（l<n<100000）。输出对于每个整数n将其分解质因数。输入样例90256199输出样例90=2*3*3*5256=2*2*2*2*2*2*2*2199=199（1）编程思路。对整数n进行分解质因数，应让变量i等于最小的质数2,然后按下述步骤完成：1） 如果i恰等于n,则说明分解质因数的过程己经结束，输出即可。2） 如果noi,但n能被i整除，则应输出i的值，并用n除以i的商，作为新的正整数n,转第1）步。3） 如果n不能被i整除，则用i+1作为新的i值，转第1）步。因此，程序主体是一个循环，在循环中根据n能否整除i,进行两种不同处理，描述为：i=2;while(i<n)(if(n%i==0)〃i〃i是n的因数，输出i//对除以因数后的商在进行分解printf(场d*“,i)n=n/i;}elsei++；i++；//找下一个因数(2)源程序。#include<stdio.h>intmain(){intnJ;while(scanf(,,%d"/&n)!=EOF)(printf(,,%d="/n);i=2；while(kn){if(n%i==O){printf("％d*“,i);n=n/i;(elsei++；)printf(,,%d\n,,/n);}return0;习题55-1完全数题目描述完全数(Perfectnumber)又称完美数或完备数，是一些特殊的自然数。它所有的真因子(即除了自身以外的约数)的和，恰好等于它本身。例如：第一个完全数是6,它有约数1、2、3、6,除去它本身6夕卜，其余3个数相加，1+2+3=6。第二个完全数是28,它有约数1、2、4、7、14、28,除去它本身28外，其余5个数相加，1+2+4+7+14=28。编写一个程序，求两个正整数之间完全数的个数。输入输入数据包含多行，第一行是一个正整数n,表示测试实例的个数，然后就是n个测试实例，每个实例占一行，由两个正整数numl和num2组成,(l<numl/num2<10000)。输出对于每组测试数据，请输出numl和num2之间(包括numl和num2)存在的完全数个数。输入样例22557输出样例01编程思路。要求numl和num2之间的所有完全数，需要对numl~num2范围内的每一个数n,计算n的所有真因子之和s,若n==s,则n就是一个完全数。框架描述为：for(n=numl;n<=num2;n++){计算n的真因子之和s:if(s==n)是完全数，计数；}为计算n的所有真因子之和s,可令s初值为1(1是n的真因子)，然后用2~n-l范围内的每个i去除n,如果n能被i整除(即n%i==O),贝iji是n的真因子，s=s+i°实际上，i(i>l)是n的真因子，则n/i也是n的真因子。因此，可以将i的范围缩小为2~而。这样，计算n的真因子之和s的操作描述为：s=l; //s为n的真因子之和for(i=2;i<=sqrt(n);i++) //求解真因子之和if(n%i=O)if(i!=n/i)s=s+i+n/i;elses=s+i;因此，程序可以写成一个嵌套的二重循环。源程序。#include<stdio.h>#include<math.h>intmain(){intt,numl,num2,i,n,s,ent;scanf("％d“,&t);while(t-){scanf(,,%d%d,,,&numl,&num2);cnt=O;if(numl>num2)(n=numl;numl=num2;num2=n;)for(n=numl;n<=num2;n++){s=l; 〃S为n的真因子之和for(i=2;i<=sqrt(n);i++) //求解真因子之和if(n%i==O)if(i!=n/i)s=s+i+n/i;elses=s+i;}if(s==n)cnt++;)printf(,,%d\n,,/cnt);}return0;5-2亲和数题目描述遥远的古代，人们发现某些自然数之间有特殊的关系：如果两个数a和b(a不等于b),a的所有真因数之和等于b,b的所有真因数之和等于a,则称a、b是一对亲和数。例如220和284,1184和1210,2620和2924,5020和5564,6232和6368。给定一个正整数S(6WSW18000),找出a,b两数中至少有一个不小于S的第一对“亲和数”。输入格式一行一个整数S。输出格式一行两个整数A和B(用空格隔开)。A表示第一个不小于S的有“亲和数”的整数，B是A的“亲和数”。输入样例#1206输出样例机220284输入样例#2260输出样例#2284220(1)编程思路。程序对输入整数begin开始的自然数进行穷举，算法描述为：for(n=begin；:n++){计算n的真因子之和s；if(s==n)continue；计算s的真因子之和m；if(m==n) //如果两数相等，是解输出解的情况;

计算自然数的真因子之和的方法，可以参见前而的习题5・1“完全数气（2）源程序。#include<stdio.h>#include<math.h>intmain(){intbegin,i,n,s,m,k;scanf(,,%d",&begin);for(n=begin;;n++){s=l;k=l;for(i=2;i<=(int)sqrt(1.0*n);i++)if(n%i==O)(s=s+i+n/i;k+=2;}i-；if(i*i==n)s-=i;if(k==l11s==n)continue;m=l;for(i=2;i<=(int)sqrt(1.0*s);i++)if(s%i==O)m+=i+s/i;i-；if(i*i==s)m-=i;if(m==n){printf(”％d%d\n",n/s)；break;〃s为n〃s为n的真因子之和〃k为n的真因子个数//求解真因子之和//若n为质数或完数，进行下次循环〃m为s的真因子之和//计算s的真因子之和//如果两数相等，输出亲和数5-3ThenumberofdivisorsaboutHumbleNumbersProblemDescriptionAnumberwhoseonlyprimefactorsare2,3,5or7iscalledahumblenumber.Thesequence1,2,3,4,5,6,7,8,9,10,12,14,15,16,18,20,21,24,25,27,...showsthefirst20humblenumbers.Nowgivenahumblenumber,pleasewriteaprogramtocalculatethenumberofdivisorsaboutthishumblenumber.Forexamle,4isahumble,andithave3divisors(l,2,4);12have6divisors.InputTheinputconsistsofmultipletestcases.Eachtestcaseconsistsofonehumblenumbernzandnisintherangeof64-bitssignedinteger.Inputisterminatedbyavalueofzeroforn.OutputForeachtestcase,outputitsdivisornumber;onelinepercase.SampleInput4120SampleOutput36编程思路。若一个大于1正整数n可以分解质因数：n=(plAal)*(p2Aa2)*(p3Aa3)*---*(pkAak),则由约数个数定理可知n的正约数有(al+l)(a2+l)(a3+l)-(ak+l)个。本题要求一个给定丑数n的约数个数，而一个丑数分解质因数后，其质因子只有2、3、5或7这4个，因此只需求出n中分别含有质因子2、3、5和7的个数即可。源程序。#include<stdio.h>intfun(—int64n,intx) //求整数n分解质因数后含质因子x的个数{intsum=0;while(n%x==0){sum++;n/=x;)returnsum;}intmain(){in