如何通过递归函数在C语言中判断一个数是否为素数？

本文共计972个文字，预计阅读时间需要4分钟。

目录+前言+思路概述+代码实现+前言+文本介绍+递归函数实现素数判断。+实际上，递归算法判断素数的本质是试除法，且递归算法在本题中并不具备优势。它不仅没有优化原始算法，还增加了额外的。

目录

• 前言
• 思路简述
• 代码实现

前言

本文介绍递归函数实现素数判断。

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

时间复杂度和空间复杂度都是0(N)，实现效率可想而知。

那为什么还要写呢？仅作为开拓思路、加深对递归函数的理解而为之。其实很多基础的算法，包括斐波那契数列、闰年等，都可以用递归实现。递归思路能将复杂的问题呈现以简单的思路，这是它的优势。通过简单问题的递归实现，大家可以提前熟悉递归的构造和运用，为后续学习数据结构“树”的相关内容作铺垫。

在实际应用中，最好还是挑选简便高效的代码实现。

题干：用递归函数判断一个自然数是否为素数。

思路简述

1. 素数：该数除了1和它本身以外不再有其他的因数（否则称为合数）。每一个比1大的整数，要么本身是一个质数，要么可以写成一系列质数的乘积。最小的质数是2。

2. 试除法

思路

1. 要判断数 i 是否为素数，由上述定义可知，需要判断除了1和它本身以外是否还有其他因数。

2. 判断方式：试除。将该数与从2到 i-1 之间所有的数除一除，看除不除得尽。