摘要

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

方法1

素數(shù)是什么

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

條件分析

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

素數(shù)是整數(shù)

素數(shù)能被自身整除

素數(shù)能被1整除

設(shè)計思路

以一道題為例——

求100到200之間的所有素數(shù)并輸出。

大體思路

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

具體代碼實現(xiàn)

#include<stdio.h>

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

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

最終結(jié)果輸出為——

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

代碼優(yōu)化

我們先解決一個數(shù)學(xué)問題——

若a為一個整數(shù)，則顯然a=√a√a，因為√a=√a，所以若有其他數(shù)cd=a，則一定存在一個數(shù)大于√a，一個數(shù)小于√a，因此大于√a之后的數(shù)字我們不需要再進(jìn)行遍歷了。
（同理，如果你不想思考這么多，寫個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++)

注：求平方根函數(shù)內(nèi)參數(shù)要求為double類型，因此先將a強(qiáng)制轉(zhuǎn)換為double型，而k是整型，所以將sqrt計算返回值再進(jìn)行強(qiáng)制轉(zhuǎn)換為int型。

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

int k;
k=(int)sqrt(1.0*a);		//1.0*a同樣將a強(qiáng)制轉(zhuǎn)換為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間的所有數(shù)字
	{
		flag = 0;				 //先假設(shè)a為素數(shù) 
		int k;
		k = (int)sqrt((double)i);
		for (b = 2; b < k; b++)	 //注意，不要忘了自身也能被整除！
		{
			if (a % b == 0)
			{
				flag = 1;  //若出現(xiàn)不能整除的情況，則令flag為1 
				break;
			}

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

方法2

我在網(wǎng)上還看到一種思路——

大體與法1（未優(yōu)化版）一致，但是沒有用標(biāo)記變量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呢？

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

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

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

個人認(rèn)為此方法不如標(biāo)記函數(shù)思路簡潔，不過仍不失為一種獨特的思路。

方法3

PS：思路不變，形式變化

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

以下是代碼實現(xiàn)——

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

int main()
{
	int a,ret;
	for (a = 100; a <= 200; a++)	//得到100到200間的所有數(shù)字
	{ 
		ret=fun(a);	 //ret為返回值，通過判斷ret的值確定a是否為素數(shù)
		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,結(jié)束 
	}
	return 0;		//若不能被整除，則返回值為0，結(jié)束 
}

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

小結(jié)

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

總結(jié) 

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

最新評論