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

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

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

3、可以改進一下，根據(jù)如果一個數(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ù)相對應(yīng)的自然數(shù)。

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

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

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

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