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

學無先后，達者為師

網站首頁 編程語言 正文

C語言求質數的幾種簡單易懂方式_C 語言

作者：我的博爾赫斯 ? 更新時間： 2023-02-02 編程語言

質數就是除了1和它本身外沒有其他因數

一. 暴力枚舉

假設現在有一個數num，要求我們判斷是否是質數，由定義知我們可以遍歷從2到 num-1的所有數，假

設都不能被整除，則num是質數，否則不是，C語言代碼實現如下。

其中track用來檢測是否遍歷完從2到num-1的所有數

int main()
{
	int n = 0;
	int track = 0;
	printf("請輸入要判斷的數: ");
	scanf("%d", &n);
	for (int i = 2; i < n; i++)
	{
		if (n % i == 0)
		{
			track = 1;
			break;
		}
	}
	if (track == 1)
		printf("這個數不是質數\n");
	else
		printf("這個數是質數\n");
	return 0;
}

二. 暴力求解的優化版本

實際上我們只需要遍歷從2到√num的數就可以了。

因為對于非質數num來說有 a * b = num；其中a和b不可能同時大于√num，也就是說num是非質數的充要條件是在 [2,num-1]的區間上有因數,根據這一點可以對代碼進行優化。

int main()
{
	int n = 0;
	int track = 0;
	printf("請輸入要判斷的數: ");
	scanf("%d", &n);
		for (int i = 2; i <= sqrt(n); i++)
		{
			if (n % i == 0)
			{
				track = 1;
				break;
			}
		}
		if (track == 1)
			printf("這個數不是質數\n");
		else
			printf("這個數是質數\n");
	
	return 0;
}

三.埃拉托斯特尼篩法

如果要求我們判斷的數字很多，那么上面兩種方法的效率就極其低下，因為每判斷一個數都要從2開始遍歷，計算機會做很多重復操作。

換一種思路，我們可以選一批質數，質數的倍數是合數（非質數），那么就可以把這些合數篩掉，經過多輪篩選后剩下的就全部是質數了。

看了前面的敘述可能有的朋友會有點懵，我解釋一下。

細節部分?

1. 怎樣選一批素數能將區間內所有合數都篩完？

從2開始到√n的所有素數。首先1肯定沒有篩選功能（1的任意倍數都是其本身）。

對于√n之后的素數，比如說用√n + 1進行篩選?，得到的可篩選的數是?[(√n + 1) *? 2, (√n +1) *?√n] 中的整數，但是這些整數都有一個小于等于√n的約數，因此在我們遍歷前面的數時已經將他們刪除掉了，所以沒必要重復，只需要 [2,√n)的所有素數即可。?

2.篩選過程具體是怎樣的？

不清楚篩選過程的朋友可以看看這張圖，這張圖搬運 自公眾號 “coder梁”，做的特別清楚。

3.具體代碼

C語言實現。

int main()
{
	//埃式篩法
	int n = 0;
	printf("請輸入要判斷的數 ");
	scanf("%d", &n);
	int* prime = (int*)malloc(n * sizeof(int));//定義一個可以存放n個數的數組
	if (!prime)
	{
		printf("創建數組失敗\n");
		exit(-1);
	}
	//將prime數組全部初始化成1，表示全部是素數
	for (int i = 0; i < n; i++)
	{
		prime[i] = 1;
	}
	//從2開始篩選
	for (int i = 2; i <= sqrt(n); i++)
	{
		if (prime[i - 1])        //如果是質數
		{
			for (int j = i * i; j <= n; j += i) //則將其剔除
				prime[j - 1] = 0;
		}
	}
	//打印
	for (int i = 0; i < n; i++)
	{
		if (prime[i] != 0)
			printf("%d ", i + 1);
	}
	printf("\n");
	return 0;
}

總結

原文鏈接：https://blog.csdn.net/qq_62236390/article/details/125699096

欄目分類
最近更新