前言

本文介紹遞歸函數(shù)實(shí)現(xiàn)素?cái)?shù)判斷。

事實(shí)上，遞歸算法判斷素?cái)?shù)的本質(zhì)是試除法，且遞歸算法在本題中并不具有優(yōu)勢(shì)。它不僅沒(méi)有優(yōu)化原算法，還增加了空間復(fù)雜度與時(shí)間復(fù)雜度。

時(shí)間復(fù)雜度和空間復(fù)雜度都是0(N)，實(shí)現(xiàn)效率可想而知。

那為什么還要寫呢？?jī)H作為開(kāi)拓思路、加深對(duì)遞歸函數(shù)的理解而為之。其實(shí)很多基礎(chǔ)的算法，包括斐波那契數(shù)列、閏年等，都可以用遞歸實(shí)現(xiàn)。遞歸思路能將復(fù)雜的問(wèn)題呈現(xiàn)以簡(jiǎn)單的思路，這是它的優(yōu)勢(shì)。通過(guò)簡(jiǎn)單問(wèn)題的遞歸實(shí)現(xiàn)，大家可以提前熟悉遞歸的構(gòu)造和運(yùn)用，為后續(xù)學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)“樹(shù)”的相關(guān)內(nèi)容作鋪墊。

在實(shí)際應(yīng)用中，最好還是挑選簡(jiǎn)便高效的代碼實(shí)現(xiàn)。

題干：用遞歸函數(shù)判斷一個(gè)自然數(shù)是否為素?cái)?shù)。

思路簡(jiǎn)述

1. 素?cái)?shù)：該數(shù)除了1和它本身以外不再有其他的因數(shù)（否則稱為合數(shù)）。每一個(gè)比1大的整數(shù)，要么本身是一個(gè)質(zhì)數(shù)，要么可以寫成一系列質(zhì)數(shù)的乘積。最小的質(zhì)數(shù)是2。

2. 試除法

思路

1. 要判斷數(shù) i 是否為素?cái)?shù)，由上述定義可知，需要判斷除了1和它本身以外是否還有其他因數(shù)。

2. 判斷方式：試除。將該數(shù)與從2到 i-1 之間所有的數(shù)除一除，看除不除得盡。若除得盡，說(shuō)明該數(shù)有除了1和它本身外的其它因數(shù)，因此它就不是素?cái)?shù)。要是除不盡，那就是素?cái)?shù)。（該部分用遞歸可以實(shí)現(xiàn)）

3. 偶數(shù)一定不是素?cái)?shù)，因而能被2模盡的數(shù)不是素?cái)?shù)。

試除法參考代碼如下

//試除法例題--打印100到200之間的素?cái)?shù)
int main()
{
	int i = 0;
	int count = 0;
	for(i=101; i<=200; i+=2)    //跳過(guò)所有的偶數(shù)
	{
		//判斷i是否為素?cái)?shù)
		//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. 將循環(huán)部分抽象成遞歸

由于每次判斷素?cái)?shù)的抽象步驟都是一樣的：取模 --> 除盡了嗎？（模為0嗎） --> 除盡了，不是素?cái)?shù) --> 沒(méi)除盡，接著除，全除完了還沒(méi)有發(fā)現(xiàn)一個(gè)能除盡的 --> 是素?cái)?shù)。

因而，改裝成如下代碼。

代碼實(shí)現(xiàn)

#include<stdio.h>
int isPrime(int num, int divide)
{
	if(num == 2)    //2是最小的質(zhì)數(shù)
		return 1;
	if(divide == 2)      //divide為2時(shí)，遞歸層數(shù)已經(jīng)很深了
		return (num % 2 != 0);    //若(num % 2)為0，則為偶數(shù)不是素?cái)?shù)，返回0（false）；
                                  //反之返回1(true)
	if(num % divide == 0)
		return 0;    //如果能除盡，就不是素?cái)?shù)
	else
		return isPrime(num, divide - 1);    //遞歸調(diào)用語(yǔ)句，含義是遍歷從2到(num-1)中的所有數(shù)
                                            //用(divide-1)實(shí)現(xiàn)模數(shù)每次遞減1，挨個(gè)遍歷
}
int main()
{
	int num;
	scanf("%d", &num);
	printf("%d", isPrime(num, num - 1));
	return 0;
}

到此這篇關(guān)于C語(yǔ)言用遞歸函數(shù)對(duì)素?cái)?shù)進(jìn)行判斷流程的文章就介紹到這了,更多相關(guān)C語(yǔ)言素?cái)?shù)判斷內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論