前言

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

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

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

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

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

題干：用遞歸函數(shù)判斷一個自然數(shù)是否為素數(shù)。

思路簡述

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

2. 試除法

思路

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

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

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

試除法參考代碼如下

//試除法例題--打印100到200之間的素數(shù)
int main()
{
	int i = 0;
	int count = 0;
	for(i=101; i<=200; i+=2)    //跳過所有的偶數(shù)
	{
		//判斷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)部分抽象成遞歸

由于每次判斷素數(shù)的抽象步驟都是一樣的：取模 --> 除盡了嗎？（模為0嗎） --> 除盡了，不是素數(shù) --> 沒除盡，接著除，全除完了還沒有發(fā)現(xiàn)一個能除盡的 --> 是素數(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ù)已經(jīng)很深了
		return (num % 2 != 0);    //若(num % 2)為0，則為偶數(shù)不是素數(shù)，返回0（false）；
                                  //反之返回1(true)
	if(num % divide == 0)
		return 0;    //如果能除盡，就不是素數(shù)
	else
		return isPrime(num, divide - 1);    //遞歸調(diào)用語句，含義是遍歷從2到(num-1)中的所有數(shù)
                                            //用(divide-1)實現(xiàn)模數(shù)每次遞減1，挨個遍歷
}
int main()
{
	int num;
	scanf("%d", &num);
	printf("%d", isPrime(num, num - 1));
	return 0;
}

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

最新評論