欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

C語言實現(xiàn)求解素數(shù)的N種方法總結(jié)

 更新時間:2023年01月21日 10:42:54   作者:博客小夢  
哈嘍各位友友們,今天又學到了很多有趣的知識,現(xiàn)在迫不及待的想和大家分享一下!本文將手把手帶領大家探討利用試除法、篩選法求解素數(shù)的n層境界!都是精華內(nèi)容,可不要錯過喲

前言

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

必備小知識

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

C語言詳解《試除法》求解素數(shù)

試除法境界1

境界1實現(xiàn)思路分析: 

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

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

境界1源碼: 

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

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

代碼結(jié)果運行圖: 

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

試除法境界2

境界2實現(xiàn)思路分析: 

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

境界2源碼: 

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

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

代碼結(jié)果運行圖: 

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

試除法境界3

境界3實現(xiàn)思路分析:

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

境界3源碼: 

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

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

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

代碼結(jié)果運行圖: 

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

試除法境界4

境界4實現(xiàn)思路分析:

  • 首先,采用境界2的算法思想。利用第一層for循環(huán)產(chǎn)生101~199的整數(shù)。
  • == 其次,利用境界三的試除想法,拿2 ~sqrt(i)的數(shù)試除。==
  • 定義flag變量,若flag為0,則不是素數(shù);若flag為1,則是素數(shù)。
  • 定義count變量,記錄試除次數(shù)。
  • 境界4算法的理性分析:境界4相比于境界3,再做優(yōu)化!先排除掉偶數(shù)。

境界4源碼: 

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

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

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

代碼結(jié)果運行圖: 

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

C語言詳解《篩選法》求解素數(shù)

預備小知識

埃拉托色尼是一名古希臘的地理學家,他是世界上第一個計算出地球周長的人。埃拉托色尼素數(shù)篩選法可以很快速的計算出1到N之間的所有素數(shù)。埃拉托色尼素數(shù)篩選法大概的計算思路是:將n開根號,即N^0.5 ,去掉2到N^0.5中所有素數(shù)的倍數(shù),剩下的數(shù)便都是素數(shù)了。例如求1到25中的素數(shù)有哪些,第一步是將25開根號,得到5;第二步將2到5的素數(shù)取出來,分別是2、3、5:再將2到25中且是2、3、5的倍數(shù)的數(shù)去掉,即去掉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中的所有素數(shù)了。從上面我們可以看出篩選法和試除法其實有著本質(zhì)上的區(qū)別,試除法是判斷每一個數(shù)是不是素數(shù)來達到目的;而篩選法不是如此,篩選法是將不是素數(shù)的數(shù)全部去除,然后得到余下的數(shù)來達到目的~

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

  • 首先,找到最小的質(zhì)數(shù)2,再把范圍內(nèi)的所有2的倍數(shù)去掉;然后接下來找次小的質(zhì)數(shù)3,再把所有3的倍數(shù)去掉;接著往復篩選去除,剩下的那些就全是素數(shù)啦!
  • 這里需要設計一個數(shù)組,只要滿足上述這些步驟,即將大于1的且是2、3、4…的倍數(shù)全部置為0。最終不是0的數(shù)就是所謂的素數(shù)啦!

篩選法境界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;//將數(shù)組先初始化存儲100到199。
                        //沒有存儲200也沒關(guān)系,200一定不是素數(shù)
        
    }
    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;
}

代碼結(jié)果運行圖: 

到此這篇關(guān)于C語言實現(xiàn)求解素數(shù)的N種方法總結(jié)的文章就介紹到這了,更多相關(guān)C語言求解素數(shù)內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!

相關(guān)文章

  • 詳解C++ 模板編程

    詳解C++ 模板編程

    模板(template)是C++實現(xiàn)泛型(Generics)和元編程(Meta Programming)的基礎。本文拋磚引玉,簡要介紹C++模板編程,不足之處敬請指正。
    2020-09-09
  • C++連接mysql數(shù)據(jù)庫(改進版)

    C++連接mysql數(shù)據(jù)庫(改進版)

    C++是大家都非常熟悉的,也是大家平時辦公中經(jīng)常會用到的,下面這篇文章主要給大家介紹了關(guān)于C++連接mysql數(shù)據(jù)庫的相關(guān)資料,文中通過代碼介紹的非常詳細,需要的朋友可以參考下
    2023-12-12
  • C++多線程編程簡單實例

    C++多線程編程簡單實例

    本文給大家分享的是C++多線程編程簡單實例,由于C++本身沒有多線程機制,在windows下我們使用調(diào)用SDK win32 api來實現(xiàn),示例都很簡單,講解的也很詳細,推薦給大家。
    2015-03-03
  • 關(guān)于《C和指針》的學習筆記

    關(guān)于《C和指針》的學習筆記

    本篇文章是對《C和指針》這本書的學習做了筆記介紹。需要的朋友參考下
    2013-05-05
  • C++ Template 基礎篇(一):函數(shù)模板詳解

    C++ Template 基礎篇(一):函數(shù)模板詳解

    這篇文章主要介紹了C++ Template函數(shù)模板,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧
    2019-04-04
  • C++實現(xiàn)LeetCode(22.生成括號)

    C++實現(xiàn)LeetCode(22.生成括號)

    這篇文章主要介紹了C++實現(xiàn)LeetCode(22.生成括號),本篇文章通過簡要的案例,講解了該項技術(shù)的了解與使用,以下就是詳細內(nèi)容,需要的朋友可以參考下
    2021-07-07
  • 詳解C語言中的rename()函數(shù)和remove()函數(shù)的使用方法

    詳解C語言中的rename()函數(shù)和remove()函數(shù)的使用方法

    這篇文章主要介紹了詳解C語言中的rename()函數(shù)和remove()函數(shù)的使用方法,是C語言入門學習中的基礎知識,需要的朋友可以參考下
    2015-09-09
  • opencv3/C++實現(xiàn)霍夫圓/直線檢測

    opencv3/C++實現(xiàn)霍夫圓/直線檢測

    今天小編就為大家分享一篇opencv3/C++實現(xiàn)霍夫圓/直線檢測,具有很好的參考價值,希望對大家有所幫助。一起跟隨小編過來看看吧
    2019-12-12
  • C語言實現(xiàn)經(jīng)典排序算法的示例代碼

    C語言實現(xiàn)經(jīng)典排序算法的示例代碼

    這篇文章主要為大家詳細介紹了如何利用C語言實現(xiàn)經(jīng)典排序算法中的冒泡排序、選擇排序、插入排序、希爾排序,文中的示例代碼講解詳細,需要的可以參考一下
    2022-08-08
  • C語言實現(xiàn)倒置字符串的兩種方法分享

    C語言實現(xiàn)倒置字符串的兩種方法分享

    這篇文章主要和大家詳細介紹了利用C語言實現(xiàn)倒置字符串的兩種方法,文中的示例代碼講解詳細,感興趣的小伙伴可以跟隨小編一起動手嘗試一下
    2022-08-08

最新評論