C語言中的素數問題為什麼求到根號某數為止

時間 2021-08-11 17:04:19

1樓:逃離

我今天也剛問了一個素數的問題。

例如一個數是m,要求它的素數,設k=sqrt(m),i=2,i<=k ,判定是否(m%i==0),

因為整數都是可以被1和自己本身整除,而素數只能給1和自己本身除。

所以我要找素數都是從2開始一個一個的找,在2

這樣編的意思就是找一個數的最小因子。且這個比if(i==m)程式的速度更快。

2樓:匿名使用者

是否是素數是用比它小的數去除它看能否出盡來判斷的,而如果能出盡的話那麼除數是成對存在的,比如22=2*11,2和11就是一對,而這一對只要判斷一個就可以了,因此這種除數判斷的下界為2,而上界為被除數開根號。

3樓:匿名使用者

舉例說明:

1. 90 = 2 * 3 * 3 * 5 (90的質因式中最大的質因數是5,小於90的平方根)

2. 49 = 7 * 7 (49 的質因式中最大的質因數是7,等於49的平方根)

總之,任意一個數的最大的質因數都小於或等於這個數的平方根。

所以,求素數時求到這個數的平方根即可,這樣可以程式提高程式效率。

4樓:

因為根號某數是可被整除無重複的數最大那個(除了本身以為),被625整除的數最大的也就是25,再大的被整除的因數中另一個肯定是2到25中某個數,因此無需繼續判斷。比如5,和125無需判斷125。

判斷一個數是否是素數,為什麼只要除到根號那個數就夠了 ,求c語言**

5樓:匿名使用者

x=ab

那麼a和b,必然有一個大於√x,一個小於(或者兩個都等於)。

那麼不是隻要判斷到√x就可以麼?

C語言的問題,為什麼是,C語言的問題,為什麼是

十進位制的7在ascii碼值表中對應的是bel bell 響鈴符 所以將其作為字元輸出時,進行了響鈴處理 給你一個ascii碼值表 bin dec hex 縮寫 字元 解釋 0000 0000 0 00 nul null 空字元 0000 0001 1 01 soh start of handing...

c語言問題求從n到m的所有素數,C語言 求n到m之間所有的素數

include int main 希望可以幫助到你!c語言 求n到m之間所有的素數 include int main if u 1 s 0 return 0 你的if u i 0 是不是有問題應該是if u i 0 你這裡是要取餘把 是餘數為0 c語言 輸出n到m之間的所有素數 對n到m之間所有數進...

c語言程式設計問題 求1到100的素數之和

include int main int i,j,k,s 0 for i 2 i 100 i k 1 for j 2 j j i j if i j 0 k 0 break s k i printf d n s return 0 程式設計 求3到100之間的素數之和 set talk off s1 0...