1、第三章第三章素数判定素数判定定理：定理：如果如果a是合数是合数, 则则a必有小于等于必有小于等于 的的真因子。真因子。证：证： 如果如果a是合数，则是合数，则a可表示成可表示成 a=bc, 其中其中1ba, 1c( )2=a, 矛盾。矛盾。aaa素数素数:整数整数p1,只有只有1和和p自身能整除自身能整除p, p为素数为素数 如如:2,3,5,7合数合数:大于大于1且不是素数的数且不是素数的数 如如:4,6,8,9/* 功能：判定功能：判定x是否是素数，是否是素数，x2 返回值：返回返回值：返回1表示是素数，返回表示是素数，返回0则不是素数则不是素数*/int is_prime(int x)
2、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是素数是素数*/素数判定算法素数判定算法【例例3-173-17】编一程序打印出编一程序打印出2 2至至9999之间的所有素数。之间的所有素数。分析：本例是上面素数判定算法的一个简单应用分析：本例是上面素数判定算法的一个简单应用#includeint is
3、_prime(int x);void main() for(i=2;i100;i=i+1) if(is_prime(i) printf(%3d,i);/*上机调试时，将上机调试时，将is_prime函数定义放在这儿函数定义放在这儿*/运行结果运行结果 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 素数家族素数家族1.梅森数梅森数: (2p-1), p为素数为素数,如如:22-1=3,27-1=1272.孪生素数孪生素数: 两个素数的差值是两个素数的差值是2, 如如2-99之间的孪生素之间的孪生素数数
4、 3.可逆素数可逆素数: 一个素数将其各位数字的顺序倒过来构成的反序一个素数将其各位数字的顺序倒过来构成的反序数也是素数数也是素数, 如如:1009,10214.回文素数回文素数: 一个素数从左到右和从右向读的结果相同且是素一个素数从左到右和从右向读的结果相同且是素数数, 如如:101,131,151,181,1915.歌德巴赫猜想歌德巴赫猜想: 任何大于任何大于4的偶数都可以表示成两个奇素数的的偶数都可以表示成两个奇素数的和和, 如如:1978=5+1973设计程序求解练习练习编程求解两个数编程求解两个数a，b的最大公约数的最大公约数如，如，GCD(8,12)=4编程求解两个数编程求解两个数
5、a，b的最小公倍数的最小公倍数如，如，LCM(20,15)=60直接思路直接思路穷举法穷举法C语言程序设计语言程序设计求最大公约数的算法求最大公约数的算法-辗转相除法辗转相除法 递推公式：递推公式： gcd(a,b)=gcd(b,a%b) 这个公式的含义是这个公式的含义是a与与b的最大公约数等于的最大公约数等于b与与a%b的最大公约数。一直递推下去，直到的最大公约数。一直递推下去，直到gcd(rn，0)，此时此时rn即为所要求的最大公约数即为所要求的最大公约数。 一个非常著名的古老算法是用于求两个整数的最大公约数一个非常著名的古老算法是用于求两个整数的最大公约数的欧几里德算法。欧几里德算法也称
6、为的欧几里德算法。欧几里德算法也称为辗转相除法辗转相除法。 C语言程序设计语言程序设计计算计算91和和52的最大公约数，求解过程如下：的最大公约数，求解过程如下：（1） mod(91,52)=39（2） mod(52,39)=13（3） mod(39,13)=0所以，所以，13就是就是91和和52的最大公约数。的最大公约数。自然语言表示的欧几里德算法如下：自然语言表示的欧几里德算法如下：输入：输入：两个正整数两个正整数m和和n输出：输出：m与与n的最大公约数的最大公约数(公因子公因子)。步骤步骤1:求余数，以求余数，以n除除m并令并令r为所得余数为所得余数(0rn)步骤步骤2:余数余数r为为0
7、吗？若吗？若r=0，算法结束；，算法结束；n即为答案即为答案步骤步骤3:互换互换,置置mn， nr，转步骤，转步骤1。C语言程序设计语言程序设计/*算法：求两个整数算法：求两个整数a和和b的最大公约数的最大公约数返回值：返回返回值：返回a和和b的最大公约数的最大公约数*/int gcd(int a,int b)int r,t;if(ab)k0=a;elsek0=b;k=k0; while( k%a !=0 | k%b !=0 ) k=k+k0;return k;C语言程序设计语言程序设计/*下面主程序用于算法测试下面主程序用于算法测试*/#includemain()int a,b; print
8、f(输入两个正整数输入两个正整数a和和b：);scanf(%d%d,&a,&b);printf(Lcm(%d,%d)=%dn,a,b,lcm(a,b);运行结果运行结果输入两个正整数输入两个正整数a和和b：23 56Lcm(23,56)=1288C语言程序设计语言程序设计【实例实例】古典问题：有一对兔子，从出生后第古典问题：有一对兔子，从出生后第3 3个月起每个个月起每个月都生一对兔子，小兔子长到第三个月后每个月又生一月都生一对兔子，小兔子长到第三个月后每个月又生一对兔子，假如兔子都不死，问每个月的兔子总数为多少？对兔子，假如兔子都不死，问每个月的兔子总数为多少？ C语言程序设计语言程序设计)
9、 3() 2(1) 1(12121nfffnfnfnnn第一个月第一个月第二个月第二个月第三个月第三个月第四个月第四个月第五个月第五个月递推公式递推公式:例例 求求Fibonacci数列：数列：1，1，2，3，5，8，的前的前40个数个数f1=1,f2=1for i=1 to 20输出f1,f2f1=f1+f2f2=f2+f11534233159710946750255142293524578241578171855377258417711121393832040570288739088169213896104181286571964181346269922746563245986321144
10、987676546368317811217830914930352102334155f1=1 (n=1)f2=1 (n=2)fn=fn-1+fn-2 (n=3)例：求例：求FibonacciFibonacci数列前数列前4040个数。个数。#include#includemain()main() long int f1=1,f2=1; long int f1=1,f2=1; int i; int i; for(i=1;i=20;i+) for(i=1;i=20;i+) printf(printf(%12ld%12ld%12ld%12ld,f1,f2);,f1,f2); f1=f1+f2; f1
11、=f1+f2; f2=f2+f1; f2=f2+f1; if(i%2=0) printf(n); 分析下面的程序分析下面的程序( (VCVC环境环境) )#include void main() int i, k,fn,fn_1=1,fn_2=1; k=2; printf(%12d%12d,fn_1,fn_2); for(i=3;i=3）,将各将各数字分开，并按其反序输出。数字分开，并按其反序输出。 分析分析: 问题的关键是如何将一个数字的各位分开？如问题的关键是如何将一个数字的各位分开？如1234，将其分解成，将其分解成1,2,3,4。初值：初值： x0=1234step1: r1=x0%1
12、0 = 4 x1=x0/10 = 123step2: r2=x1%10 = 3 x2=x1/10 = 12step3: r3=x2%10 = 2 x3=x2/10 = 1step4: r4=x3%10 = 1 x4=x3/10 = 0 程序程序:#includevoid main() int x,r; scanf(%d,&x); while(x!=0) r=x%10; x=x/10; printf(%d,r); printf(n); 递推公式递推公式: :运行结果运行结果输入一个整数：输入一个整数：5353443535例：打印出所有的例：打印出所有的“水仙花数水仙花数”（一个（一个3 3位数，
13、其各位数，其各位数字的立方和等于该数本身。位数字的立方和等于该数本身。153=1153=13 3+5+53 3+3+33 3）#include stdio.hvoid main( ) int i,j,k,n;for (n=100;n1000;n+)i=n/100; /*百位数百位数*/j=n/10-i*10; /*十位数十位数*/k=n%10; /*个位数个位数*/if(n=i*i*i+j*j*j+k*k*k) printf(%dn,n); 运行结果：运行结果：153 370 371 407【例例】 编一程序求出满足不等式编一程序求出满足不等式的最小的最小n n值。值。分析：分析：（1 1）此
14、题不等式左边和式中的数据项（求和项）个）此题不等式左边和式中的数据项（求和项）个数是未知的，也正是数是未知的，也正是需要求出的的需要求出的的n n。因此。因此用用whilewhile循环比较方便循环比较方便。（2 2）对于和式中的每个数据项（求和项），）对于和式中的每个数据项（求和项），i=1,2,.ni=1,2,.n，可采用，可采用循环累加循环累加的方法来计算出不等的方法来计算出不等式的和。式的和。（3 3）设）设循环变量为循环变量为i i，它应从，它应从1 1开始取值，每次增加开始取值，每次增加1 1，直到不等式的值不小于直到不等式的值不小于5 5为止，此时的为止，此时的i i值就是所求值
15、就是所求的的n n。设累加和用变量。设累加和用变量s s表示，在循环体内应把表示，在循环体内应把1/i1/i的值的值累加到累加到s s上上。5131211n采用采用while循环编写循环编写出程序如下：出程序如下： #include void main() int i=0; double s=0; while(s5) i+ s = s + 1.0/i; printf(n=%dn,i); 5131211n采用采用for循环编写循环编写程序，则如下所示：程序，则如下所示： #include void main() int i; double s=0; for(i=1; s5; i+) s=s+1.
16、0/i; printf(n=%dn,i-1); /*注意：此注意：此i-1的值为所求的的值为所求的n值值*/ 该程序的输出结果应为：该程序的输出结果应为：n=835131211n【例例】( (非线性方程求根非线性方程求根) )编一程序求编一程序求解方程解方程e ex x+3x-2=0+3x-2=0的根，要求两相邻近的根，要求两相邻近似根之差的绝对值不大于似根之差的绝对值不大于0.0010.001。分析：分析：（1）令）令f(x)=ex+3x-2，根据函数的泰勒展开原理，将，根据函数的泰勒展开原理，将 函数函数f(x)在任意在任意x0处展开式为：处展开式为： )( )(! 21)( )()()(
17、020000 xfxxxfxxxfxf线性逼近线性逼近,代入方程代入方程)( )(000 xfxfxx0)( )()()(000 xfxxxfxf)( )(111iiiixfxfxx迭代公式迭代公式:（2）由上面迭代公式可知，）由上面迭代公式可知，新的近似根新的近似根只与只与刚求出的近似根刚求出的近似根有关。有关。 所以可设置两个变量，假定分别为所以可设置两个变量，假定分别为x1和和x2，用，用x2保存新的近似根保存新的近似根，用，用x1保存已求出保存已求出的近似根的近似根。 在每次计算新的近似根前，都要把在每次计算新的近似根前，都要把x2的的值赋给值赋给x1，然后再根据公式，然后再根据公式
18、x2=x1-f(x1)/f(x1)计算出新的近似根计算出新的近似根x2。)( )(111iiiixfxfxx#include#includedouble fun(double x); /*函数函数f(x)*/double dfun(double x); /*f(x)的导数的导数f(x) */double Newton(double x0) double x1,x2,y1,y2,eps=0.001; x2=x0; /*给给x2赋初值为赋初值为x0*/ do x1=x2; y1=fun(x1); /*y1=f(x1)*/ y2=dfun(x1); /*y2=f(x1)*/ x2=x1-y1/y2;
19、 while(fabs(x2-x1)eps); return x2; )( )(111iiiixfxfxx本例函数本例函数f(x)及其导数定义如下：及其导数定义如下：double fun(double x) return exp(x)+3*x-2 ; double dfun(double x) return exp(x)+3 ; 下面写一个主函数，以测试上面的算法。下面写一个主函数，以测试上面的算法。void main() float x; printf(请输入任一实数作为自变量请输入任一实数作为自变量x的初值的初值:); scanf(%f,&x); x=Newton(x); /*调用求根算法
20、调用求根算法*/ printf(root=%8.3fn,x);程序运行结果：程序运行结果：请输入任一实数作为自变量请输入任一实数作为自变量x的初值的初值:2root= 0.242求解过程的可视化求解过程的可视化.7656543432122关键关键: :寻找规律寻找规律, ,找到通项找到通项!1.! 31!21! 111ne习题61111435710 用公 式 求的 近 似 值 ， 直 到最 后 一 项 的 绝 对 值 小 于为 止t=1,pi=0,n=1.0,s=1当|t|1e-6pi=pi+tn=n+2s=-st=s/npi=pi*4输出pi分子：1，-1，1，-1分母：1，3，5，7，.设
21、设: t为每项值为每项值 pi为各项累加值为各项累加值 s:每项前的符号每项前的符号 n:为每项分母值为每项分母值思路：凡是遇到求若干个有规律变化的项的乘积思路：凡是遇到求若干个有规律变化的项的乘积,就可在循就可在循环体中用环体中用求累乘积求累乘积的的编程通式编程通式t=t*x来编程实现；求其和来编程实现；求其和,用用求累加和求累加和的的编程通式编程通式s=s+x来编程实现来编程实现,其中其中t 、s分别为累积、分别为累积、累和累和,初值分别为初值分别为t=1,s=0,x为变化的项的通式。为变化的项的通式。为止最后一项的绝对值小于的近似值，直到公式求例用61071513114t=1,pi=0,n=1.0,s=1当当|t| 1e-6pi=pi+tn=n+2s=-st=s/npi=pi*4输出输出pi练习作业练习作业熟练掌握本熟练掌握本ppt中的常见题型，并能用中的常见题型，并能用C语语言编程解决问题。言编程解决问题。习题习题 3-13, 3-14, 3-18利用定义函数模块实现：习题利用定义函数模块实现：习题 3-15
