哈嘍,大家好~~~我是小編田甜，關(guān)于輸入一個(gè)正整數(shù)判斷是否為素?cái)?shù)，判斷是否為素?cái)?shù)這個(gè)很多人還不知道,那么現(xiàn)在讓田甜帶著大家一起來看看吧！

1、判斷是否是質(zhì)數(shù)最直觀和簡(jiǎn)單的方法就是從2開始直接除，能除盡（余數(shù)為0）就不是質(zhì)數(shù)。

2、則C語言實(shí)現(xiàn)為：int isprime(int m){int i;for(i=2;i

3、可以改進(jìn)一下，根據(jù)如果一個(gè)數(shù)是合數(shù)，那么它的最小質(zhì)因數(shù)肯定小于等于它的平方根。

4、用反證法可以證明一下。

5、假設(shè)x是n的最小質(zhì)因數(shù)，則存在n/x=p。

6、p>x,x*p=n。

7、如果x不小于等于它的平方根，則x*x>n,而p>x，故x*p>n,假設(shè)不成立。

8、合數(shù)是與質(zhì)數(shù)相對(duì)應(yīng)的自然數(shù)。

9、一個(gè)大于1的自然數(shù)如果它不是合數(shù)，則它是質(zhì)數(shù)。

10、也就是說如果一個(gè)數(shù)能被它的最小質(zhì)因數(shù)整除的話，那它肯定是合數(shù)，即不是質(zhì)數(shù)。

11、所以判斷一個(gè)數(shù)是否是質(zhì)數(shù)，只需判斷它是否能被小于它開跟號(hào)后的所有數(shù)整除，因此，這樣做的運(yùn)算少了很多，降低了時(shí)間復(fù)雜度。

本文分享完畢，希望對(duì)大家有所幫助哦。

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