_基本程序设计(周).pptVIP

第三章 #includestdio.h void main() { int x,i; printf(请输入一个整数，若小于3则重输:); do scanf(“%d”,x); while(x=2); i=2; do { while(x%i==0) { printf(“%d ”,i); x=x/i; } i++; }while(ix); if(x!=1) printf(“%d\n”,x); } 假定x=24，按程序执行过程，手工演算一遍： i x x%i 动作 2 24 0 执行内循环，输出2，x=12 2 12 0 执行内循环，输出2，x=6 (x=x/i) 2 6 0 执行内循环，输出2，x=3 (x=x/i) 2 3 1 退出内循环，i=i+1 3 3 0 执行内循环，输出3，x=1 3 1 1 退出内循环，i=4,ix,退出外循环 到此，程序的输出结果是“2 2 2 3”，读者可以进一步取x的不同值进行手工操作，例如，x=50时，输出是“2 5 5”。 因式分解 【例3-11】从键盘上输入的一个大于等于3的整数,将其分解为质因子的乘积。例如： 输入：28，输出：2 2 7 输入：37，输出：37 【例3-16】 #includestdio.h #includemath.h void num_decomp(int n); main() { int n; printf(“请输入n=”); scanf(“%d”,n); num_decomp(n); printf(\n); } 【例3-16】 void num_decomp(int n) { int i,p; printf(%d=,n); if(n0) { printf(-); n=abs(n); } for(i=2;i=sqrt(n);i++) { p=0; while(n%i==0) { n=n/i; p=p+1; } if (p==1) printf((%d),i); else if (p1) printf((%d^%d),i,p); } if(n!=1) printf((%d),n); } 素数判定 定理：如果a是合数, 则a必有小于等于 的真因子。 证： 如果a是合数，则a可表示成 a=bc, 其中1ba, 1ca. 显然, b和c中必有一个小于等于 ，否则, bc( )2=a, 矛盾。 素数判定算法 /********************************************** 功能：判定x是否是素数，x≥2 返回值：返回1表示是素数，返回0则不是素数 ***********************************************/ int is_prime(int x) { int m; if(x==2) 　return 1; if(x%2==0) return 0; /*偶数不是素数*/ m=sqrt(x); for(i=3;i=m;i++) if (x%i==0) /*x能被i整除，x不是素数*/ return 0; return 1; /*循环结束还没有返回，说明x是素数*/ } 【