前言🙌? ?
博客昵稱:博客小夢😊
最喜歡的座右銘:全神貫注的上吧?。?!
作者簡介:一名熱愛C/C++,算法等技術(shù)、喜愛運(yùn)動、熱愛K歌、敢于追夢的小博主!
博主小留言:哈嘍!😄各位的uu們,我是你的博客好友小夢,希望我的文章可以給您帶來一定的幫助,話不多說,文章推上!歡迎大家在評論區(qū)嘮嗑指正,覺得好的話別忘了一鍵三連哦!😘
必備小知識~😘? ? 哈嘍各位友友們😊,我今天又學(xué)到了很多有趣的知識,現(xiàn)在迫不及待的想和大家分享一下!😘我僅已此文,手把手帶領(lǐng)大家探討利用試除法、篩選法求解素?cái)?shù)的n層境界!都是精華內(nèi)容,可不要錯過喲?。?!😍😍😍
C語言詳解《試除法》求解素?cái)?shù)🙌 試除法境界1~ 😊? ?質(zhì)數(shù)又稱素?cái)?shù)。一個大于1的自然數(shù),除了1和它自身外,不能被其他自然數(shù)整除的數(shù)叫做質(zhì)數(shù);否則稱為合數(shù)(規(guī)定1既不是質(zhì)數(shù)也不是合數(shù))。這里以求解100~200之間的素?cái)?shù)舉例講解😊
境界1實(shí)現(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,則不是素?cái)?shù);若flag為1,則是素?cái)?shù)。
- 定義count變量,記錄試除次數(shù)。
- 境界1算法的理性分析:境界1,簡單來說就是讓每一個數(shù)i和2~ i-1的數(shù)試除,這是最簡單的想法,但是算法的效率是最低的~
看了文字的描述,大家可能理解的還是不夠深刻。這里俺親自敲出代碼輔助大家理解~ 😊
境界1源碼: 😍
#includeint main()
{ int count = 0;//記錄試除次數(shù)
int i = 0;
int j = 0;
for (i = 100; i<= 200; i++)
{int flag = 1;//flag最終結(jié)果為1,表示i是素?cái)?shù),為0表示不是素?cái)?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é)果運(yùn)行圖: 😍
由境界1求解100~200之間的素?cái)?shù),需要試除3292次?。?!可見其算法效率如何啦。
試除法境界2~😊境界2實(shí)現(xiàn)思路分析: 😍
- 首先利用第一層for循環(huán)產(chǎn)生101~199的整數(shù),這是和境界1最本質(zhì)的區(qū)別!為什么這樣設(shè)計(jì)呢?原因很簡單,因?yàn)?00到200之間的偶數(shù)一定不是素?cái)?shù),可以不用參與試除過程。
- 其次,利用第二層for循環(huán)產(chǎn)生2~ i - 1之間的整數(shù),并讓101到199之間的每一個數(shù)和2到 i -1之間的整數(shù)試除。
- 定義flag變量,若flag為0,則不是素?cái)?shù);若flag為1,則是素?cái)?shù)。
- 定義count變量,記錄試除次數(shù)。
- 境界2算法的理性分析:境界2和境界1類似,就是讓每一個數(shù)i和2~ i-1的數(shù)試除,但是境界2能夠提前讓一些本不可能是素?cái)?shù)的整數(shù)(100—200間的偶數(shù))提前排除掉~
境界2源碼: 😍
#includeint main()
{ int count = 0;//記錄試除次數(shù)
int i = 0;
int j = 0;
for (i = 101; i< 200; i+=2)//提前排除100到200之間的偶數(shù),符合這個條件一定不是素?cái)?shù)。
{int flag = 1;//flag最終結(jié)果為1,表示i是素?cái)?shù),為0表示不是素?cái)?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é)果運(yùn)行圖: 😍
由境界2求解100~200之間的素?cái)?shù),需要試除3241次,稍微比境界1好那么一丟丟啦!但是其算法效率還是不盡人意。
試除法境界3~😊境界3實(shí)現(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è)計(jì)呢?
設(shè)計(jì)思路分析:因?yàn)槿魏我粋€不是素?cái)?shù)的數(shù)即合數(shù),都一定可以進(jìn)行因式分解。這里已16舉例說明,16 = 2 * 8 = 4 * 4 。因此如果16被2整除就可以判定16不是素?cái)?shù)了,就不用那2到 i - 1的每一個數(shù)都試除一遍啦。因此,只需要拿2 ~sqrt(i)的數(shù)試除即可,這樣大大提高了算法的效率!- 定義flag變量,若flag為0,則不是素?cái)?shù);若flag為1,則是素?cái)?shù)。
- 定義count變量,記錄試除次數(shù)。
- 境界3算法的理性分析:境界3相比于前面兩種境界,做了很大的改進(jìn)!讓每一個數(shù)試除的測試減少了至少一半,大大減少了試除的次數(shù),從而大大提高了算法的效率?。?!
境界3源碼: 😍
#include#includeint main()
{int count = 0;//記錄試除次數(shù)
int i = 0;
int j = 0;
for (i = 100; i<= 200; i++)
{int flag = 1;//flag最終結(jié)果為1,表示i是素?cái)?shù),為0表示不是素?cái)?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é)果運(yùn)行圖: 😍
由境界4求解100~200之間的素?cái)?shù),只需要試除393次,相比于境界1和境界2的算法效率來說,已經(jīng)有長足的改進(jìn)啦!
境界4實(shí)現(xiàn)思路分析:
- 首先,采用境界2的算法思想。利用第一層for循環(huán)產(chǎn)生101~199的整數(shù)。
- == 其次,利用境界三的試除想法,拿2 ~sqrt(i)的數(shù)試除。==
- 定義flag變量,若flag為0,則不是素?cái)?shù);若flag為1,則是素?cái)?shù)。
- 定義count變量,記錄試除次數(shù)。
- 境界4算法的理性分析:境界4相比于境界3,再做優(yōu)化!先排除掉偶數(shù)。
境界4源碼: 😍
#include#includeint main()
{int count = 0;//記錄試除次數(shù)
int i = 0;
int j = 0;
for (i = 101; i< 200; i += 2)//排除100到200之間的2的倍數(shù),符合這個條件一定不是素?cái)?shù)。
{int flag = 1;//flag最終結(jié)果為1,表示i是素?cái)?shù),為0表示不是素?cái)?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é)果運(yùn)行圖: 😍
由境界4求解100~200之間的素?cái)?shù),試除總次數(shù)為342,是,綜合考慮了境界2和境界3的改良思想,已經(jīng)達(dá)到了試除法的最高境界啦!
? ?埃拉托色尼是一名古希臘的地理學(xué)家,他是世界上第一個計(jì)算出地球周長的人。埃拉托色尼素?cái)?shù)篩選法可以很快速的計(jì)算出1到N之間的所有素?cái)?shù)。埃拉托色尼素?cái)?shù)篩選法大概的計(jì)算思路是:將n開根號,即N^0.5 ,去掉2到N^0.5中所有素?cái)?shù)的倍數(shù),剩下的數(shù)便都是素?cái)?shù)了。例如求1到25中的素?cái)?shù)有哪些,第一步是將25開根號,得到5;第二步將2到5的素?cái)?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中的所有素?cái)?shù)了。從上面我們可以看出篩選法和試除法其實(shí)有著本質(zhì)上的區(qū)別,試除法是判斷每一個數(shù)是不是素?cái)?shù)來達(dá)到目的;而篩選法不是如此,篩選法是將不是素?cái)?shù)的數(shù)全部去除,然后得到余下的數(shù)來達(dá)到目的~
篩選法境界5~😊境界5(基礎(chǔ)篩選法)實(shí)現(xiàn)思路分析:
- 首先,找到最小的質(zhì)數(shù)2,再把范圍內(nèi)的所有2的倍數(shù)去掉;然后接下來找次小的質(zhì)數(shù)3,再把所有3的倍數(shù)去掉;接著往復(fù)篩選去除,剩下的那些就全是素?cái)?shù)啦!
- 這里需要設(shè)計(jì)一個數(shù)組,只要滿足上述這些步驟,即將大于1的且是2、3、4…的倍數(shù)全部置為0。最終不是0的數(shù)就是所謂的素?cái)?shù)啦!
境界5源碼: 😍
#includeint 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一定不是素?cái)?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é)果運(yùn)行圖: 😍
? ?本篇文章旨在帶領(lǐng)大家利用C語言相關(guān)知識求解素?cái)?shù)n種境界。希望大家通過閱讀此文有所收獲!😘如果我寫的有什么不好之處,請?jiān)谖恼孪路浇o出你寶貴的意見😊。如果覺得我寫的好的話請點(diǎn)個贊贊和關(guān)注哦~😘
你是否還在尋找穩(wěn)定的海外服務(wù)器提供商?創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級流量清洗系統(tǒng)配攻擊溯源,準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性,企業(yè)級服務(wù)器適合批量采購,新人活動首月15元起,快前往官網(wǎng)查看詳情吧
網(wǎng)頁標(biāo)題:你是真的“C”——C語言詳解求素?cái)?shù)n種境界~-創(chuàng)新互聯(lián)
標(biāo)題路徑:http://muchs.cn/article2/eesic.html
成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián),為您提供外貿(mào)建站、動態(tài)網(wǎng)站、網(wǎng)站維護(hù)、企業(yè)網(wǎng)站制作、品牌網(wǎng)站建設(shè)、面包屑導(dǎo)航
聲明:本網(wǎng)站發(fā)布的內(nèi)容(圖片、視頻和文字)以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主,如果涉及侵權(quán)請盡快告知,我們將會在第一時間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場,如需處理請聯(lián)系客服。電話:028-86922220;郵箱:631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載,或轉(zhuǎn)載時需注明來源: 創(chuàng)新互聯(lián)
猜你還喜歡下面的內(nèi)容