递归函数实现素数判断

简介: 该文介绍了素数判断的递归实现,尽管递归算法在判断素数上并不高效,时间复杂度和空间复杂度均为O(N),但作为学习和理解递归的一种方式,仍有其价值。文章强调在实际应用中应选择更高效的方法。递归思路基于试除法,对于大于1的整数,如果只能被1和自身整除,则为素数。递归函数通过不断试除2到根号下该数之间的数来判断,同时注意到偶数不是素数。文中给出了非递归和递归的试除法代码示例。

前言


素数判断是编程语言学习过程中一个老生常谈的话题,而它的实现也有多种算法,经典的试除法(以及试除法的几种优化),进阶的素数表筛选法,埃拉托斯特尼筛法和欧拉筛法(以及它们的优化)等。对以上算法感兴趣的朋友们,不妨搜索“素数判断的N种境界”来学习了解。


事实上,递归算法判断素数的本质是试除法,且递归算法在本题中并不具有优势。它不仅没有优化原算法,还增加了空间复杂度与时间复杂度。


时间复杂度和空间复杂度都是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;
}



相关文章
|
7天前
递归函数
【6月更文挑战第9天】递归函数。
17 4
|
18天前
|
算法 C语言
C语言中的递归调用与递归函数
C语言中的递归调用与递归函数
17 0
|
1月前
递归阶乘详解
递归阶乘详解
13 1
|
1月前
|
C语言
递归求阶乘
【1月更文挑战第18天】C语言实例——递归求阶乘。
26 1
|
8月前
尾递归
尾递归是一种递归函数优化技术,它指的是在递归函数的最后一步操作中,调用自身并返回结果,而不进行任何其他操作。尾递归可以有效地减少递归调用的次数,从而提高程序的执行效率。
31 5
|
9月前
|
算法
递归函数(详解+实战)
递归函数(详解+实战)
|
12月前
|
机器学习/深度学习
递归函数问题
递归函数问题
45 0
|
12月前
|
机器学习/深度学习 算法
使用递归方法和for循环方法求阶乘
使用递归方法和for循环方法求阶乘
122 0
|
Java 编译器 Python
聊聊递归函数
我们知道在一个函数内部是可以调用其他函数。那么如果一个函数在内部调用函数自身,这个函数就是递归函数。
186 0