日本免费高清视频-国产福利视频导航-黄色在线播放国产-天天操天天操天天操天天操|www.shdianci.com

學無先后，達者為師

網站首頁 編程語言 正文

C語言用遞歸函數對素數進行判斷流程_C 語言

作者：碳基肥宅 ? 更新時間： 2022-11-12 編程語言

前言

本文介紹遞歸函數實現素數判斷。

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

時間復雜度和空間復雜度都是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;
}

原文鏈接：https://blog.csdn.net/wyd_333/article/details/125928695

欄目分類
最近更新