首頁 > 軟體

C語言實現求解素數的N種方法總結

2023-01-22 14:00:10

前言

哈嘍各位友友們,我今天又學到了很多有趣的知識,現在迫不及待的想和大家分享一下!我僅已此文,手把手帶領大家探討利用試除法、篩選法求解素數的n層境界!都是精華內容,可不要錯過喲!!!

必備小知識

質數又稱素數。一個大於1的自然數,除了1和它自身外,不能被其他自然數整除的數叫做質數;否則稱為合數(規定1既不是質數也不是合數)。這裡以求解100~200之間的素數舉例講解

C語言詳解《試除法》求解素數

試除法境界1

境界1實現思路分析: 

  • 首先,利用第一層for迴圈產生100~200的整數;
  • 其次,利用第二層for迴圈產生2~ i - 1之間的整數,並讓100到200之間的每一個數和2到 i - 1之間的整數試除。
  • 定義flag變數,若flag為0,則不是素數;若flag為1,則是素數。
  • 定義count變數,記錄試除次數。
  • 境界1演演算法的理性分析:境界1,簡單來說就是讓每一個數i和2~ i-1的數試除,這是最簡單的想法,但是演演算法的效率是最低的~

看了文字的描述,大家可能理解的還是不夠深刻。這裡俺親自敲出程式碼輔助大家理解~ 

境界1原始碼: 

#include<stdio.h>
int main()
{
    
    int count = 0;//記錄試除次數
    int i = 0;
    int j = 0;
    for (i = 100; i <= 200; i++)
    {
        int flag = 1;//flag最終結果為1,表示i是素數,為0表示不是素數。
        for (j = 2; j < i; j++)
        {
            count++;
            if (i % j == 0)
            {
                flag = 0;
                break;
            }

        }
        if(flag == 1)
        printf("%d ", i);
    }
    printf("n境界1試除總次數:%d", count);
    return 0;
}

程式碼結果執行圖: 

由境界1求解100~200之間的素數,需要試除3292次!!!可見其演演算法效率如何啦。

試除法境界2

境界2實現思路分析: 

  • 首先利用第一層for迴圈產生101~199的整數,這是和境界1最本質的區別!為什麼這樣設計呢?原因很簡單,因為100到200之間的偶數一定不是素數,可以不用參與試除過程。
  • 其次,利用第二層for迴圈產生2~ i - 1之間的整數,並讓101到199之間的每一個數和2到 i -1之間的整數試除。
  • 定義flag變數,若flag為0,則不是素數;若flag為1,則是素數。
  • 定義count變數,記錄試除次數。
  • 境界2演演算法的理性分析:境界2和境界1類似,就是讓每一個數i和2~ i-1的數試除,但是境界2能夠提前讓一些本不可能是素數的整數(100—200間的偶數)提前排除掉~

境界2原始碼: 

#include<stdio.h>
int main()
{
    
    int count = 0;//記錄試除次數
    int i = 0;
    int j = 0;
    for (i = 101; i < 200; i+=2)//提前排除100到200之間的偶數,符合這個條件一定不是素數。
    {
        int flag = 1;//flag最終結果為1,表示i是素數,為0表示不是素數。
        for (j = 2; j < i; j++)
        {
            count++;
            if (i % j == 0)
            {
                flag = 0;
                break;
            }

        }
        if(flag == 1)
        printf("%d ", i);
    }
    printf("n境界2試除總次數:%d", count);
    return 0;
}

程式碼結果執行圖: 

由境界2求解100~200之間的素數,需要試除3241次,稍微比境界1好那麼一丟丟啦!但是其演演算法效率還是不盡人意。

試除法境界3

境界3實現思路分析:

  • 首先,利用第一層for迴圈產生100~200的整數;
  • 其次,利用第二層for迴圈產生2~ sqrt(i)之間的整數,並讓101到199之間的每一個數和2到 sqrt(i)之間的整數試除。為什麼這樣設計呢?設計思路分析:因為任何一個不是素數的數即合數,都一定可以進行因式分解。這裡已16舉例說明,16 = 2 * 8 = 4 * 4 。因此如果16被2整除就可以判定16不是素數了,就不用那2到 i - 1的每一個數都試除一遍啦。 因此,只需要拿2 ~sqrt(i)的數試除即可,這樣大大提高了演演算法的效率!
  • 定義flag變數,若flag為0,則不是素數;若flag為1,則是素數。
  • 定義count變數,記錄試除次數。
  • 境界3演演算法的理性分析:境界3相比於前面兩種境界,做了很大的改進!讓每一個數試除的測試減少了至少一半,大大減少了試除的次數,從而大大提高了演演算法的效率!!!

境界3原始碼: 

#include<stdio.h>
#include<math.h>
int main()
{

	int count = 0;//記錄試除次數
	int i = 0;
	int j = 0;
	for (i = 100; i <= 200; i++)
	{
		int flag = 1;//flag最終結果為1,表示i是素數,為0表示不是素數。
		for (j = 2; j <= sqrt(i); j++)//只需要試除2到sqrt(i)之間的整數即可
		{
			count++;
			if (i % j == 0)
			{
				flag = 0;
				break;
			}

		}
		if (flag == 1)
			printf("%d ", i);
	}
	printf("n境界3試除總次數:%d", count);
	return 0;
}

程式碼結果執行圖: 

由境界4求解100~200之間的素數,只需要試除393次,相比於境界1和境界2的演演算法效率來說,已經有長足的改進啦!

試除法境界4

境界4實現思路分析:

  • 首先,採用境界2的演演算法思想。利用第一層for迴圈產生101~199的整數。
  • == 其次,利用境界三的試除想法,拿2 ~sqrt(i)的數試除。==
  • 定義flag變數,若flag為0,則不是素數;若flag為1,則是素數。
  • 定義count變數,記錄試除次數。
  • 境界4演演算法的理性分析:境界4相比於境界3,再做優化!先排除掉偶數。

境界4原始碼: 

#include<stdio.h>
#include<math.h>
int main()
{

	int count = 0;//記錄試除次數
	int i = 0;
	int j = 0;
	for (i = 101; i < 200; i += 2)//排除100到200之間的2的倍數,符合這個條件一定不是素數。
	{
		int flag = 1;//flag最終結果為1,表示i是素數,為0表示不是素數。
		for (j = 2; j <= sqrt(i); j++)//只需要試除2到sqrt(i)之間的整數即可
		{
			count++;
			if (i % j == 0)
			{
				flag = 0;
				break;
			}

		}
		if (flag == 1)
			printf("%d ", i);
	}
	printf("n境界4試除總次數:%d", count);
	return 0;
}

程式碼結果執行圖: 

由境界4求解100~200之間的素數,試除總次數為342,是,綜合考慮了境界2和境界3的改良思想,已經達到了試除法的最高境界啦!

C語言詳解《篩選法》求解素數

預備小知識

埃拉托色尼是一名古希臘的地理學家,他是世界上第一個計算出地球周長的人。埃拉托色尼素數篩選法可以很快速的計算出1到N之間的所有素數。埃拉托色尼素數篩選法大概的計算思路是:將n開根號,即N^0.5 ,去掉2到N^0.5中所有素數的倍數,剩下的數便都是素數了。例如求1到25中的素數有哪些,第一步是將25開根號,得到5;第二步將2到5的素數取出來,分別是2、3、5:再將2到25中且是2、3、5的倍數的數去掉,即去掉4、6、8、9、10、12、14、15、16、18、 20、21、22、24、25;剩下2、3、5、7、11、13、17、19便是1到25中的所有素數了。從上面我們可以看出篩選法和試除法其實有著本質上的區別,試除法是判斷每一個數是不是素數來達到目的;而篩選法不是如此,篩選法是將不是素數的數全部去除,然後得到餘下的數來達到目的~

境界5(基礎篩選法)實現思路分析:

  • 首先,找到最小的質數2,再把範圍內的所有2的倍數去掉;然後接下來找次小的質數3,再把所有3的倍數去掉;接著往復篩選去除,剩下的那些就全是素數啦!
  • 這裡需要設計一個陣列,只要滿足上述這些步驟,即將大於1的且是2、3、4…的倍數全部置為0。最終不是0的數就是所謂的素數啦!

篩選法境界5

境界5原始碼: 

#include<stdio.h>
int main()
{
    int i = 0;
    int j = 0;
    int arr[100];
    int count = 0;
    for (i = 0; i < 100; i++)
    {
        arr[i] = 100 + i;//將陣列先初始化儲存100到199。
                        //沒有儲存200也沒關係,200一定不是素數
        
    }
    for (i = 0; i < 100; i++)
    {
        j = i + 1;
        while (j > 1)
        {
            count++;
            if (arr[i] % j == 0)
                arr[i] = 0;
            j = j - 1;
        }
    }
    for (j = 1; j < 100; j++)
    {
        if (arr[j] != 0)
        {
            printf("%d ", arr[j]);
        }
    }
    return 0;
}

程式碼結果執行圖: 

到此這篇關於C語言實現求解素數的N種方法總結的文章就介紹到這了,更多相關C語言求解素數內容請搜尋it145.com以前的文章或繼續瀏覽下面的相關文章希望大家以後多多支援it145.com!


IT145.com E-mail:sddin#qq.com