首頁 >> 要聞 >

判斷是否為素數(shù)的公式(判斷是否為素數(shù))

2023-06-07 02:30:07 來源: 用戶: 

關(guān)于判斷是否為素數(shù)的公式,判斷是否為素數(shù)這個問題很多朋友還不知道,今天小六來為大家解答以上的問題,現(xiàn)在讓我們一起來看看吧!

1、關(guān)于素數(shù)的判定 所謂“篩選法”指的是“埃拉托色尼(Eratosthenes)篩法”。

2、他是古希臘的著名數(shù)學(xué)家。

3、他采取的方法是,在一張紙上寫上1到100全部整數(shù),然后逐個判斷它們是否是素數(shù),找出一個非素數(shù),就把它挖掉,最后剩下的就是素數(shù)。

4、 具體做法如下: <1> 先將1挖掉(因為1不是素數(shù))。

5、 <2> 用2去除它后面的各個數(shù),把能被2整除的數(shù)挖掉,即把2的倍數(shù)挖掉。

6、 <3> 用3去除它后面的各數(shù),把3的倍數(shù)挖掉。

7、 <4> 分別用4、5…各數(shù)作為除數(shù)去除這些數(shù)以后的各數(shù)。

8、這個過程一直進(jìn)行到在除數(shù)后面的數(shù)已全被挖掉為止。

9、例如找1~50的素數(shù),要一直進(jìn)行到除數(shù)為47為止(事實上,可以簡化,如果需要找1~n范圍內(nèi)素數(shù)表,只需進(jìn)行到除數(shù)為n^2(根號n),取其整數(shù)即可。

10、例如對1~50,只需進(jìn)行到將50^2作為除數(shù)即可。

11、) 如上算法可表示為: <1> 挖去1; <2> 用剛才被挖去的數(shù)的下一個數(shù)p去除p后面各數(shù),把p的倍數(shù)挖掉; <3> 檢查p是否小于n^2的整數(shù)部分(如果n=1000, 則檢查p<31?),如果是,則返回(2)繼續(xù)執(zhí)行,否則就結(jié)束; <4> 紙上剩下的數(shù)就是素數(shù)。

12、 #include #include int main(void) { int i; int j; int a[101]; // 為直觀表示,各元素與下標(biāo)對應(yīng),0號元素不用 for (i = 1; i <= 100; i++) // 數(shù)組各元素賦值 a[i] = i; for (i = 2; i < sqrt(100); i++) // 外循環(huán)使i作為除數(shù) for (j = i + 1; j <= 100; j++) // 內(nèi)循環(huán)檢測除數(shù)i之后的數(shù)是否為i的倍數(shù) { if (a[i] != 0 && a[j] != 0) // 排除0值元素 if (a[j] % a[i] == 0) a[j] = 0; // i后數(shù)若為i的倍數(shù),剛將其置0(挖去) } int n = 0; // 對輸出素數(shù)計數(shù), 以控制換行顯示 for (i = 2; i <= 100; i++) // 輸出素數(shù) { if (a[i] != 0) { printf("%-5d", a[i]); // 輸出數(shù)組中非0元素(未挖去的數(shù)) n++; } if (n == 10) { printf(""); // 每行10個輸出 n = 0; } } printf(""); return 0; } 運(yùn)行結(jié)果(VC): ================================================= 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 =================================================。

本文分享完畢,希望對大家有所幫助。

  免責(zé)聲明:本文由用戶上傳,與本網(wǎng)站立場無關(guān)。財經(jīng)信息僅供讀者參考,并不構(gòu)成投資建議。投資者據(jù)此操作,風(fēng)險自擔(dān)。 如有侵權(quán)請聯(lián)系刪除!

 
分享:
最新文章
大家愛看
頻道推薦
站長推薦