C语言素数判断
碳基肥宅 人气:0前言
本文介绍递归函数实现素数判断。
事实上,递归算法判断素数的本质是试除法,且递归算法在本题中并不具有优势。它不仅没有优化原算法,还增加了空间复杂度与时间复杂度。
时间复杂度和空间复杂度都是0(N),实现效率可想而知。
那为什么还要写呢?仅作为开拓思路、加深对递归函数的理解而为之。其实很多基础的算法,包括斐波那契数列、闰年等,都可以用递归实现。递归思路能将复杂的问题呈现以简单的思路,这是它的优势。通过简单问题的递归实现,大家可以提前熟悉递归的构造和运用,为后续学习数据结构“树”的相关内容作铺垫。
在实际应用中,最好还是挑选简便高效的代码实现。
题干:用递归函数判断一个自然数是否为素数。
思路简述
1. 素数:该数除了1和它本身以外不再有其他的因数(否则称为合数)。每一个比1大的整数,要么本身是一个质数,要么可以写成一系列质数的乘积。最小的质数是2。
2. 试除法
思路
1. 要判断数 i 是否为素数,由上述定义可知,需要判断除了1和它本身以外是否还有其他因数。
2. 判断方式:试除。将该数与从2到 i-1 之间所有的数除一除,看除不除得尽。若除得尽,说明该数有除了1和它本身外的其它因数,因此它就不是素数。要是除不尽,那就是素数。(该部分用递归可以实现)
3. 偶数一定不是素数,因而能被2模尽的数不是素数。
试除法参考代码如下
//试除法例题--打印100到200之间的素数 int main() { int i = 0; int count = 0; for(i=101; i<=200; i+=2) //跳过所有的偶数 { //判断i是否为素数 //2->i-1 int j = 0; for(j=2; j<=sqrt(i); j++) { if(i%j == 0) break; } if(j > sqrt(i)) { count++; printf("%d ", i); } } printf("\ncount = %d\n", count); return 0; }
4. 将循环部分抽象成递归
由于每次判断素数的抽象步骤都是一样的:取模 --> 除尽了吗?(模为0吗) --> 除尽了,不是素数 --> 没除尽,接着除,全除完了还没有发现一个能除尽的 --> 是素数。
因而,改装成如下代码。
代码实现
#include<stdio.h> int isPrime(int num, int divide) { if(num == 2) //2是最小的质数 return 1; if(divide == 2) //divide为2时,递归层数已经很深了 return (num % 2 != 0); //若(num % 2)为0,则为偶数不是素数,返回0(false); //反之返回1(true) if(num % divide == 0) return 0; //如果能除尽,就不是素数 else return isPrime(num, divide - 1); //递归调用语句,含义是遍历从2到(num-1)中的所有数 //用(divide-1)实现模数每次递减1,挨个遍历 } int main() { int num; scanf("%d", &num); printf("%d", isPrime(num, num - 1)); return 0; }
加载全部内容