C語言中判斷素?cái)?shù)(求素?cái)?shù))的思路與方法實(shí)例
前言
素?cái)?shù)又稱質(zhì)數(shù)。所謂素?cái)?shù)是指除了 1 和它本身以外,不能被任何整數(shù)整除的數(shù),例如17就是素?cái)?shù),因?yàn)樗荒鼙?2~16 的任一整數(shù)整除。
思路1):因此判斷一個(gè)整數(shù)m是否是素?cái)?shù),只需把 m 被 2 ~ m-1 之間的每一個(gè)整數(shù)去除,如果都不能被整除,那么 m 就是一個(gè)素?cái)?shù)。
思路2):判斷方法還可以簡化。m 不必被 2 ~ m-1 之間的每一個(gè)整數(shù)去除,只需被 2 ~ 之間的每一個(gè)整數(shù)去除就可以了。如果 m 不能被 2 ~ 間任一整數(shù)整除,m 必定是素?cái)?shù)。例如判別 17 是是否為素?cái)?shù),只需使 17 被 2~4 之間的每一個(gè)整數(shù)去除,由于都不能整除,可以判定 17 是素?cái)?shù)。
原因:因?yàn)槿绻?m 能被 2 ~ m-1 之間任一整數(shù)整除,其二個(gè)因子必定有一個(gè)小于或等于 ,另一個(gè)大于或等于 。例如 16 能被 2、4、8 整除,16=2*8,2 小于 4,8 大于 4,16=4*4,4=√16,因此只需判定在 2~4 之間有無因子即可。
思路1實(shí)現(xiàn):
#include <stdio.h> int main() { int n; printf("請輸入一個(gè)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是素?cái)?shù)\n", n); } else { printf("%d不是素?cái)?shù)\n", n); } return 0; }
思路2實(shí)現(xiàn):
#include <stdio.h> #include <math.h> int main() { int n; printf("請輸入一個(gè)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是素?cái)?shù)\n", n); } else { printf("%d不是素?cái)?shù)\n", n); } return 0; }
《C與指針》4.14 - 2:
打印1~100之間所有質(zhì)數(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; }
結(jié)果:
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
補(bǔ)充:判斷素?cái)?shù)的4種方法實(shí)例
#include<stdio.h> #include<math.h> //方法一:從1-n挨個(gè)判斷; bool isPrimel_1(int n) { for(int i=2;i<n;i++) if(n%i==0) return false; return true; } //方法二: 將被判斷數(shù)n,進(jìn)行開方作為判斷結(jié)束的條件, //因?yàn)殚_方后的數(shù),是n的最大因子,最大因子之后的數(shù)對判斷該數(shù)是否是素?cái)?shù)沒有意義。 bool isPrimel_2(int n) { for(int i=2;i<sqrt(n);i++) if(n%i==0) return false; return true; } //方法三: 只需要判斷到該數(shù)的一半即可,如果超過它本身的一半, //進(jìn)行求余的結(jié)果將永遠(yuǎn)不會(huì)為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ù),先對一個(gè)數(shù)進(jìn)行奇偶判斷,若是奇數(shù), //只對從3到它本身的奇數(shù)進(jìn)行求余計(jì)算,同理若是偶數(shù),一定不是素?cái)?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("請輸入一個(gè)數(shù):"); scanf("%d",&n); printf("%d,%d,%d,%d\n",isPrimel_1(n),isPrimel_2(n),isPrimel_3(n),isPrimel_4(n)); return 0; }
總結(jié)
到此這篇關(guān)于C語言中判斷素?cái)?shù)(求素?cái)?shù))的文章就介紹到這了,更多相關(guān)C語言判斷素?cái)?shù)內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
C語言 數(shù)據(jù)結(jié)構(gòu)堆排序順序存儲(chǔ)(升序)
這篇文章主要介紹了C語言 數(shù)據(jù)結(jié)構(gòu)堆排序順序存儲(chǔ)(升序)的相關(guān)資料,需要的朋友可以參考下2017-05-05C語言中字符串與各數(shù)值類型之間的轉(zhuǎn)換方法
這篇文章主要介紹了C語言中字符串與各數(shù)值類型之間的轉(zhuǎn)換方法,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2021-03-03總結(jié)了24個(gè)C++的大坑,你能躲過幾個(gè)
這篇文章主要介紹了總結(jié)了24個(gè)C++的大坑,你能躲過幾個(gè),小編覺得挺不錯(cuò)的,現(xiàn)在分享給大家,也給大家做個(gè)參考。一起跟隨小編過來看看吧2021-05-05