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