C語言中判斷素數(shù)(求素數(shù))的思路與方法實例
前言
素數(shù)又稱質數(shù)。所謂素數(shù)是指除了 1 和它本身以外,不能被任何整數(shù)整除的數(shù),例如17就是素數(shù),因為它不能被 2~16 的任一整數(shù)整除。
思路1):因此判斷一個整數(shù)m是否是素數(shù),只需把 m 被 2 ~ m-1 之間的每一個整數(shù)去除,如果都不能被整除,那么 m 就是一個素數(shù)。
思路2):判斷方法還可以簡化。m 不必被 2 ~ m-1 之間的每一個整數(shù)去除,只需被 2 ~ 之間的每一個整數(shù)去除就可以了。如果 m 不能被 2 ~ 間任一整數(shù)整除,m 必定是素數(shù)。例如判別 17 是是否為素數(shù),只需使 17 被 2~4 之間的每一個整數(shù)去除,由于都不能整除,可以判定 17 是素數(shù)。
原因:因為如果 m 能被 2 ~ m-1 之間任一整數(shù)整除,其二個因子必定有一個小于或等于 ,另一個大于或等于 。例如 16 能被 2、4、8 整除,16=2*8,2 小于 4,8 大于 4,16=4*4,4=√16,因此只需判定在 2~4 之間有無因子即可。
思路1實現(xiàn):
#include <stdio.h> int main() { int n; printf("請輸入一個1-100之間的整數(shù):\n"); scanf("%d", &n); int m = 0; for (int i = 2; i < n; i++ ) { if(n % i == 0) { m++; } } if (m == 0) { printf("%d是素數(shù)\n", n); } else { printf("%d不是素數(shù)\n", n); } return 0; }
思路2實現(xiàn):
#include <stdio.h> #include <math.h> int main() { int n; printf("請輸入一個1-100之間的整數(shù):\n"); scanf("%d", &n); int i = 0; int q = sqrt(n); for (i = 2; i <= q; i++ ) { if(n % i == 0) { break; } } if (i > q) { printf("%d是素數(shù)\n", n); } else { printf("%d不是素數(shù)\n", n); } return 0; }
《C與指針》4.14 - 2:
打印1~100之間所有質數(shù):
#include <stdio.h> int main() { int num, divisor; printf("1, 2"); for (num = 3; num <= 100; num += 2) { for(divisor = 3; divisor < num; divisor +=2 ) { if (num % divisor == 0) { break; } } if(divisor >= num) { printf(", %d", num); } } printf("\n"); return 0; }
結果:
1, 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
補充:判斷素數(shù)的4種方法實例
#include<stdio.h> #include<math.h> //方法一:從1-n挨個判斷; bool isPrimel_1(int n) { for(int i=2;i<n;i++) if(n%i==0) return false; return true; } //方法二: 將被判斷數(shù)n,進行開方作為判斷結束的條件, //因為開方后的數(shù),是n的最大因子,最大因子之后的數(shù)對判斷該數(shù)是否是素數(shù)沒有意義。 bool isPrimel_2(int n) { for(int i=2;i<sqrt(n);i++) if(n%i==0) return false; return true; } //方法三: 只需要判斷到該數(shù)的一半即可,如果超過它本身的一半, //進行求余的結果將永遠不會為0,除非是該數(shù)對該數(shù)的求余。 bool isPrimel_3(int n) { int i; if(n%2==0) return 0; for(i=3;i=n/2;i+=2){ if(n%i==0) return 0; return 1; } } //方法四:從3-n,只判斷奇數(shù),先對一個數(shù)進行奇偶判斷,若是奇數(shù), //只對從3到它本身的奇數(shù)進行求余計算,同理若是偶數(shù),一定不是素數(shù)。 bool isPrimel_4(int n) { int i,j=1; if(n%2==0) return 0; else{ for(i=3;i<=n;i=i+2){ if(n%i==0) j=i; break; } } if(j==n) return 0; return 1; } int main() { int n; printf("請輸入一個數(shù):"); scanf("%d",&n); printf("%d,%d,%d,%d\n",isPrimel_1(n),isPrimel_2(n),isPrimel_3(n),isPrimel_4(n)); return 0; }
總結
到此這篇關于C語言中判斷素數(shù)(求素數(shù))的文章就介紹到這了,更多相關C語言判斷素數(shù)內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家!