《数论与c语言编程》由会员分享，可在线阅读，更多相关《数论与c语言编程（31页珍藏版）》请在金锄头文库上搜索。
1、数论与C语言编程,苏州科技学院天平学院基础部,目录,1、歌德巴赫猜想 2、数的基本知识（约数、倍数、质数、合数和自然数） 3、质数（素数）、完全数、陷阱数、互满数对、可分解的整数、特殊4位正整数、Troisky数等 4、相关的C语言基础函数： 素数、回文数、经典函数 求因子分解之和 求因子分解之积（字符串形式） 练习1、编写求正整数重排后的最大或最小值程序 练习2、编写求取10000以内的完全数 练习3、编写歌德巴赫猜想小于100的偶数是两个质数之和的程序 练习4、编写输出小于M的所有可分解的整数的程序 练习5、编写特殊四位正整数的程序,数学皇冠上的明珠：歌德巴赫猜想,1、任何大于2的偶数都是
2、两个质数之和,2、陈景润在1966年证明“歌德巴赫猜想”的“1 + 2”，也就是： “一个大偶数可以表示为一个素数和一个不超过两个素数的乘积之和”,返 回,1 2 3 4 5 6 7 8 9 10 11 12,1 的约数：,的约数： ,的约数： ,的约数： ,的约数： ,的约数： ,的约数： ,的约数： ,的约数： ,10的约数： 10,11的约数： 11,12的约数： 12,请你对这12个数按约数的个数进行分类,只有一个约数的 只有两个约数的 有两个以上约数的 的约数： 的约数： 的约数： 的约数： 的约数： 的约数： 的约数： 的约数： 的约数： 11的约数： 11 10的约数： 10 1
3、2 的约数： 12 质数 合数,下面同学的座号，哪些是质数，哪些是合数。 17 22 29 35 37 87,17 、 29、 37 是质数。,22 、 35 、 87是合数。,判断,学校有教师135人。其中男教师56 人；女教师有79 人；高级教师67 人。 实验小学有44个教学班。学生数2628人。 质数 合数,79,67,56,135,44,2628,结论：最小质数为67；最小合数为44,试一试：制作100以内的质数表,1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 3
4、2 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100,100以内的质数表：,2,4,0,3,5,7,9,10以内最大的质数,最小的质数,最小的合数,既是5的倍数又是5的约数,最小的偶数或最小自然数,最小的质数又是奇数,10以内最大的奇、合数
5、,质数是永恒的谜 质数把自己打扮一番，混在自然数里，使人很难从外表看出它有什么特征。比如：101，401，601，701都是质数，但是301和901却不是质数。又比如：11是质数，但由11个1、13个1、17个1排成的数都不是质数，而19个1、23个1排成的数却都是质数。 17世纪，数学家们仔细研究了下面这些特殊结构的数：31，331，3331，33331，333331，3333331，33333331。发现这些数都是质数，因而推出这种结构的数都是质数。可是没想到，下一个这种数就是合数： 3333333311719607843 自然数中有多少个质数？人们还不清楚，因为它的规律很难寻找。它像一个
6、顽皮的孩子一样，东躲西藏，和数学家捉迷藏呢。,在自然数1中： 奇数有： 偶数有： 质数有： 合数有：,1 3 5 7 9 11 13 15 17 19,2 4 6 8 10 12 14 16 18 20,2 3 5 7 11 13 17 19,4 6 8 9 10 12 14 15 16 18 20,数论部份结束,返 回,结论：最小的质数是：2 最小的合数是：4 最小的自然数是：0 例，若m=21，求大于m，并且不包括小于m的质数因子的最小合数的值。 解： int i; while(+m) for(i=m/2;i1;i-) if(m%i=0) if(m%2!=0,有趣的数之一：,回文数：有些数
7、不管是从左往右读，还是从右往左读，读出的结果都相同。例如：10201等 质数(或称素数)：除了被1和本身数能除尽外，其他数均不能除尽它。例如3、5、7等 回文质数(或称回文素数) 有些质数不管是从左往右读，还是从右往左读，读出的结果都相同。例如：131、151、181、191、313、 正倒质数(或称绝对素数) 1331 7997 157751 12311321 去尾质数(或称超级素数) 有些质数，不断去尾后，留下的数仍是质数。例如： 599595 2339233232 斩头质数(或称超级素数) 有些质数，不断斩头后，留下的数仍是质数。例如： 317177 2647647477 孪生质数 在质
8、数序列中，除了2以外都是奇数。如果两个相邻的奇数都是质数，那么就称这两个质数是孪生质数。这种孪生质数多吗？我们找找看。100以内的孪生质数只有：3，5； 5，7； 11，13； 17，19； 29，31； 41，43； 59，61；71，73。 随着自然数的越来越大，质数也就越来越难找。因此，孪生质数就更 难找了。,有趣的数之二,完全数：若一个正整数x的所有因子（包括1，但不包括x本身）之和等于x自身，则称此数为完全数。例如：28的因子为1、2、4、7、14且1+2+4+7+14=28，因此28是一个完全数，10000以内完全数有：6、28、496、8128 超完全数：超完全数是指具有下以下特
9、性的整数N：(N)=2N，其中(N)表示整数N的所有因子之和（因子包括N自身）。例如16的所有因子之和为31（1+2+4+8+16=31），31的所有因子之和为32（1+31=32），而32=216，因此16是一个超完全数。 黑洞数：又称陷阱数，是类具有奇特转换特性的整数。任何一个数字不全相同整数，经有限次“重排求差”操作，总会得某一个或一些数，这些数即为黑洞数。“重排求差“操作即组成该数得排后的最大数去重排的最小数。在一份科学杂志上看到印度数学家研究过四位黑洞数，得到的四位黑洞数为6174。 在三位数里，495也是一个黑洞数。对任何一个不完全相同的三位数，只要进行如上的重排和求差，几步之后就
10、会得出495。 互满数对：如果数a的真因子之和等于数b，且数b的真因子之和等于数a，则称(a,b)为一对互满数。例如(220,284)是一对互满数，因为220的真因子之和为284(1+2+4+5+10+11+20+22+44+55+110=284),且284的真因子之和为220(1+2+4+71+142=220)。,有趣的数之三:可分解的整数,可分解的整数：可分解的整数是指这个整数的所有数位上的数字之和等于该数的所有素数因子的各位数字之和。例如9975是一个可分解整数，该数的所有数位上的数字之和为30（9+9+7+5=30）；该数的所有素数因子是3、5、5、7、19（355719=9975），
11、所有素数因子的各位数字之和为30（3+5+5+7+1+19）=30）。（2006秋完善程序第14题）,返 回,有趣的数之四:特殊四位整数,特殊四位整数： 寻找具有下列特性的四位整数，其百位数为0，去掉百位数0可得到一个三位正整数，而该正整数乘以9等于原四位正整数。例如，6075=6759，所以6075是具有上述特性的正整数。 (2007秋完善程序第13题),返 回,Troisky数,2008秋C01编程题：找出符合以下条件的Troitsky数：将该数的首位数字移到末位数字之后得到的数是原数的整数倍。例如：将142857的首位数字1移到末位之后得到的数是428571=3142857，因此1428
12、57是Troitsky数。 编写函数int Troitsky( long a)，其功能是求出1 000 000以内的Troitsky数，并将它们依次放入a指向的数组中。函数返回找到的Troitsky数的个数。 【测试数据与运行结果】142857 285714 int change_int_array(long n,int a) long z=n; int k=0; while(z0) ak+=z%10; z=z/10; return k; int Troitsky(long a) int i,j,m=0,s=0, b10; long k, temp; for(k=10000;k=0;i-) t
13、emp=temp*10+bi; temp=temp*10+bj-1; /*将该数的首位数字移到末位数字*/ if(temp%k=0 ,返 回,素数(质数)C程序 从键盘输入一个正整数，判别是否是质数？ 函数prime()是典型的正整型量是否是质数的标准函数（对于长整型量，需修改int为long）,#include #include int prime(int x) int flag=1,i; for(i=(int)sqrt(x);i1;i-) if(x%i=0) flag=0; break; return flag; main() int x; scanf(“%d“, ,返 回,回文数C程序中
14、倒序数生成方法之一,方法之一:简便 #include main() long x=123578,y=0,z; z=x; while(z0) y=y*10+z%10; z=z/10; printf(“nx=%dny=%dn“,x,y); ,回文数C程序中倒序数生成方法之二,#include int plalindrome(long x) int i=0,j=0, a10,flag=1; long n; n=x; while(n!=0) aj+=n%10; n=n/10; j-; while(ij) if(ai=aj) i+,j-; else flag=0; return flag; return
15、 flag; main() long m; scanf(“%ld“, ,方法二复杂。但其中将数分解到整型数组中的方法，又可用于下列场合：在黑洞数中“重排求差”操作即组成该数重排后的最大数去重排的最小数； 也可用于编程题要求将矩阵中最大值重新按递减或递增排列的场合。,回文数的应用-2007秋C02编程题,编写子函数要求： void change(long x, int n)，对x指向的数组中前n个整数做如下变换：从前向后后依次判断每个整数及该整数的平方是否均为回文数（回文数是指一个数的反序数等于该数自身），若是，则将该整数移到最后的数之后，若不是，则保持该整数的存储位置不变。例如，1012=10201，101和10201均为回文数，因此101是需要被移动的数。此外101、121
