摘要

本文介紹了判斷素數的3種方法，從素數的概念分析，確定找到素數的幾個必要條件，設計思路，并將代碼進行優(yōu)化。此外，還使用自定義函數的形式將同樣的思路進行實現。

方法1

素數是什么

素數，就是僅能被自身和1整除的數字。

條件分析

首先我們可以提取出判斷素數的三個基本條件：

素數是整數

素數能被自身整除

素數能被1整除

設計思路

以一道題為例——

求100到200之間的所有素數并輸出。

大體思路

• 遍歷
  • 首先，得到100到200間的所有數字（記為a）——for循環(huán)
  • 當 A%B==0時說明A被B整除了
  • 根據兩個基本條件——a能被1整除，且a能被自身整除，所以除數（記為b）應為2到a-1間的所有數字——for循環(huán)
• 設置判斷條件
  • 當a%b==0時a不是素數
  • 設置標記變量flag，當a%b==0時令flag=1；后續(xù)循環(huán)沒必要進行，因此設置break；結束該循環(huán)。
  • 特別注意flag何時初始化為0

具體代碼實現

#include<stdio.h>

int main()
{
	int a, b, flag;
	for (a = 100; a <= 200; a++)	//得到100到200間的所有數字
	{
		flag = 0;				 //先假設a為素數 
		for (b = 2; b < a; b++)	 //注意，不要忘了自身也能被整除！
		{
			if (a % b == 0)
			{
				flag = 1;  //若出現不能整除的情況，則令flag為1 
				break;
			}

		}						//標記變量——flag
		if (0 == flag)
			printf("%d ", a);
	}
	return 0;
}

最終結果輸出為——

101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199

代碼優(yōu)化

我們先解決一個數學問題——

若a為一個整數，則顯然a=√a√a，因為√a=√a，所以若有其他數cd=a，則一定存在一個數大于√a，一個數小于√a，因此大于√a之后的數字我們不需要再進行遍歷了。
（同理，如果你不想思考這么多，寫個b<n/2也比全部遍歷好多了）

因此第二個循環(huán)：

for (b = 2; b < a; b++)

我們可以優(yōu)化為——

int k;
k=(int)sqrt((double)a);	
for (b = 2; b < a; b++)

注：求平方根函數內參數要求為double類型，因此先將a強制轉換為double型，而k是整型，所以將sqrt計算返回值再進行強制轉換為int型。

或者用不那么繞的寫法——

int k;
k=(int)sqrt(1.0*a);		//1.0*a同樣將a強制轉換為double型
for (b = 2; b < a; b++)

所以優(yōu)化之后的代碼為——

#include<stdio.h>
#include<math.h>	//sqrt在math.h頭文件中

int main()
{
	int a, b, flag;
	for (a = 100; a <= 200; a++)	//得到100到200間的所有數字
	{
		flag = 0;				 //先假設a為素數 
		int k;
		k = (int)sqrt((double)i);
		for (b = 2; b < k; b++)	 //注意，不要忘了自身也能被整除！
		{
			if (a % b == 0)
			{
				flag = 1;  //若出現不能整除的情況，則令flag為1 
				break;
			}

		}						//標記變量——flag
		if (0 == flag)
			printf("%d ", a);
	}
	return 0;
}

方法2

我在網上還看到一種思路——

大體與法1（未優(yōu)化版）一致，但是沒有用標記變量flag，而是判斷最終b是否等于a——

#include<stdio.h>

int main()
{
	int a, b;
	for (a = 100; a <= 200; a++)	
	{
		for (b = 2; b < a; b++)	
		{
			if (a % b == 0)
			break;
		}					
		if (b == a)	  //反正要全部遍歷一遍，不如把代碼寫得短一點~
			printf("%d ", a);
	}
	return 0;
}

注意：判斷最終的b是否等于a

這里為何判斷的是b等于a而非b等于a-1呢？

例如：當a=101時，進入第二個for循環(huán)，進行大量遍歷后來到b=100，此時經過if判斷同樣不滿足條件，不進入if語句。

然后就要b++，得到b=101，那么b=101時不滿足b<a的條件，所以不再進入for循環(huán)，直接進入判斷if（b= =a）語句，此時b與a相等。
走到這一步，說明a除了自身與1外沒有能被a整除的除數，因此a為素數。

簡言之，條件表達式的執(zhí)行次數總是比循環(huán)體的執(zhí)行次數多一次。

個人認為此方法不如標記函數思路簡潔，不過仍不失為一種獨特的思路。

方法3

PS：思路不變，形式變化

我們可以將給定一個數字a，判斷其是否為素數的這段邏輯封裝在一個自定義函數中。

以下是代碼實現——

#include<stdio.h>
int fun(int a);

int main()
{
	int a,ret;
	for (a = 100; a <= 200; a++)	//得到100到200間的所有數字
	{ 
		ret=fun(a);	 //ret為返回值，通過判斷ret的值確定a是否為素數
		if(ret==0)
		printf("%d ",a);
	}
	return 0;
}
int fun(int a)
{	int b;
	for (b = 2; b < a; b++)	
	{
		if (a % b == 0)
		return 1;	//若能被整除，則返回值為1,結束 
	}
	return 0;		//若不能被整除，則返回值為0，結束 
}

注意 return 1; 和 return 0; 的位置。

小結

• 判斷素數起碼有三種方法
• 特別注意標記函數的使用，靈活運行用自定義函數，注意分析for循環(huán)的邏輯順序，注意break;使用的位置，注意sqrt函數的參量類型及頭文件，注意簡化遍歷次數、優(yōu)化方案的思路。

總結 

到此這篇關于C語言素數(質數)判斷的3種方法的文章就介紹到這了,更多相關C語言素數質數判斷內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

最新評論