判斷是否為素數python_判斷是否為素數_焦點熱門

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

2、他是古希臘的著名數學家。

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

(資料圖)

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

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

6、 <3> 用3去除它后面的各數，把3的倍數挖掉。

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

8、這個過程一直進行到在除數后面的數已全被挖掉為止。

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

10、例如對1～50，只需進行到將50^2作為除數即可。

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

12、 #include #include int main(void) { int i; int j; int a[101]; // 為直觀表示，各元素與下標對應，0號元素不用 for (i = 1; i <= 100; i++) // 數組各元素賦值 a[i] = i; for (i = 2; i < sqrt(100); i++) // 外循環使i作為除數 for (j = i + 1; j <= 100; j++) // 內循環檢測除數i之后的數是否為i的倍數 { if (a[i] != 0 && a[j] != 0) // 排除0值元素 if (a[j] % a[i] == 0) a[j] = 0; // i后數若為i的倍數，剛將其置0(挖去) } int n = 0; // 對輸出素數計數, 以控制換行顯示 for (i = 2; i <= 100; i++) // 輸出素數 { if (a[i] != 0) { printf("%-5d", a[i]); // 輸出數組中非0元素(未挖去的數) n++; } if (n == 10) { printf(""); // 每行10個輸出 n = 0; } } printf(""); return 0; } 運行結果(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 =================================================。

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