Download presentation
Presentation is loading. Please wait.
1
计算机三级考试C语言上机试题专题
2
素 数 问 题 判断一个数是否是素数的方法 (1) 算法设计 (2) 算法分析 (3) 算法流程图 (4) C程序代码
3
第一部分 —— 算法设计 如果某个自然数n是素数，那么可能存在这样的情况——在2~n/2范围内没有一个自然数k能够整除n。所以，如果要判断自然数n是否为一个素数，只需要让n不断的去除以从2开始的，到n/2结束的整数k，这是一个反复执行的操作。如果在这个范围内的数没有一个k能够整除n，就说明n是一个素数。反之，只需要存在一个k能够整除n，就说明n不是一个素数。
4
第二部分——算法的分析： （1）首先输入一个需要判定的自然数n （2）接着，我们设置一个除数变量，同时也是一个计数变量k，将其初值设置为2 （3）使用第一个判断框，设置循环的条件为“k<=n/2” ，循环中判断n mod k的值，如果不为零，继续循环；如果为零，直接跳出循环 （4）循环结束通过k的值确定n是否是素数
5
算法流程图:
6
判断素数的C程序: void IsPrime(int n) { int k; printf("输入一个正整数："); scanf("%d",&n); for(k=2;k<=n/2;k++) if(n%k==0) break; if(k>n/2) printf("%d是一个素数。",n); else printf("%d不是一个素数。",n); }
7
程序的改进： 通过证明,只需判断在2—sqrt(n)范围内没有一个自然数k能够整除n，就能证明n是素数 for(k=2;k<=sqrt(n);k++) if(n%k==0) break; 例子：
Similar presentations
