1樓:_____一葉障目
去搜尋乙個演算法交mr判素,全名miller-robin演算法,這個演算法是基於費馬小定理的素數測試方法。
它適用於對於一些單獨的數進行素數測試。
至於篩法,搜一下就找到演算法了,篩法適用於求n以內的所有素數~望採納~
2樓:匿名使用者
老實說,2到10,000,000是個很小的區間,對於計算機程式設計而言幾乎不算什麼。預先生成乙個素數表,然後查表即可,不需要動態寫演算法去驗證。
在你程式開始時,採用打洞的方法首先建立素數表,然後對於每組輸入查表即可。
所謂打洞:就是對於所有的數
首先把2的倍數去掉
然後把3的倍數
然後把5的倍數
直到所有的數的倍數都去掉
至於具體怎麼寫,就看你自己水平了
3樓:匿名使用者
//樓上提到的篩選法求1-100之間的素數。
#include
#include
#define n 101
void main()
printf("\n");
for (i=2,line=0;i 4樓:匿名使用者 篩法求質數 自己上網去搜 c語言中素數的判斷方法 5樓:五四公社 介紹三種使用c語言來判斷素數的方法,以及用做素數表來判斷找素數的方法。 6樓:匿名使用者 求素數的方法很多,其中最簡單的一種就是除以它之前的所有數(從2開始),如果都不能整除, 它就是乙個素數。這個是根據素數的定義求解的,只能被1和它本身整除。 但顯然這樣的效率是不高的,如果要求1-100內的素數,對每乙個數除以之前所有的數,有很多優化的餘地。 比如除以素數就可以了,沒必要去除以合數,於是加乙個表,把之前的結果儲存下來,利用空間換取時間。 對於素數的判定,其實只需要判定是否能被 sqrt(n) 以內的素數整除。 感性上講,對於n,要麼是質數,只能被1和自己整除,要麼能分解質因數,至少有兩個素數因子。 n=p..q 因為不可能p和q都大於sqrt(n)(否則乘積就大於n了),所以只需要判斷那個小的素數能不能被n整除就可以了。 這樣,把求素數的演算法又提高了一步,不過計算中大量的用到除法,除法效率一般比較低。 有一種篩法求素數的演算法,把1-n排成一排,從2開始,2的倍數肯定不是素數,去除,剩下的數中下乙個是3. 再把3的倍數去除,再下乙個是5(4已經去除了),以此類推,最後剩下的數必然是素數,因為 它沒有被篩,不是任何乙個數的倍數(除了1和自己)。這樣只需要很多次加法就可以了。 例如乙個求 3000000 以內的素數的程式:#include #include using namespace std; const int max=3000000; char table[max]; void cal_prime()}} }int main() return 0; }複製**這算是基本的篩法了,它更是以空間換取時間,因為記憶體中存的表不只是素數,還有合數的空間,合數比素數多得多。。。 它也有很多優化的餘地,比如6,在2的時候篩掉一次。在3的時候又篩掉一次。篩選的時候,乙個數之所以能被篩去兩次, 它至少是兩個質數的倍數,每個質因數篩選一次。通過一定程度上減少重複,可以提公升演算法的效率。 對於這種演算法的改進,有一種更直接的演算法,線性篩選,就是對乙個合數,就進行一次篩選,極大程度的減少重複計算。 同樣條件**如下:#include #include using namespace std; const int max=3000000; char table[max]; int prime[max]; int num = 0; void cal_prime()}} int main() return 0; }複製**這個演算法又多了兩倍的空間儲存質數,還好這樣空間複雜度也是o(n)。 演算法中關鍵點是 if ( i % prime[j] == 0 ) break; 沒有這句這個跟篩法就差不多了,主要是防止重複篩除。 這個應該算是求素數最快的確定性演算法了,不過感覺用途也不是非常大,除了學習跟玩之外。。。 一般素數的應用在加密領域,利用乙個數分解成兩個大素數的積非常難的性質, 數論上大數非常大,陣列是不可能放下1-n個數的(定址都不行了)。這點上這個演算法還沒有 之前直接除的演算法實用,最起碼一直等還是能出來結果的。。。 不過在應用的時候可以利用費馬小定理試探素數,雖然有一定出錯的概率,但是概率非常小, 實際中是能夠容忍的。 費馬小定理雖然證明是錯的,但是總還有不少概率是對的。。。 簡單說演算法是 判斷 2^(n-1) % n == 1 是否成立,成立則基本可認為是素數。(要是整數只能算32以內的素數了, 所以先得有個大整數運算的類,沒有寫過高效的大整數實現,演算法也停留在理論 ⊙﹏⊙b汗。。。) (費馬定理是 a^(n-1) % n == 1 對所有 a < n 的正整數成立。這個小定理算是逆命題特化,不過 是錯的。。。) 7樓:魏子棟 需要自己根據素數的數學定義,自行書寫素數判斷函式並呼叫。 1、素數的判斷。 根據素數定義,除了1和本身不存在其它約數的正整數為素數。 所以在c語言中判斷n是否為素數可以從2開始到到n-1逐一嘗試,如果可以整除說明不是素數。 更進一步,可以從2判斷到n/2或者n的算術平方根,如果不存在約數,那麼即為素數。 除此以外,判斷素數的演算法還有素數篩等。 2、函式編寫: 以遍歷判斷約數的方法為例,函式可以編寫如下: int isprime(int n)//判斷n是否為素數,如果是則返回1,否則返回0. 3、以輸入乙個整數值,判斷是否為素數,並輸出結果,完整程式如下: #include #include int isprime(int n)//判斷n是否為素數,如果是則返回1,否則返回0. int main() 注意,用到了平方根函式sqrt,所以需要包含標頭檔案math.h 8樓:匿名使用者 從大於m的數迴圈,讓每個數x從2到sqrt(x)(x的開方取整)看是否存在約數,如果有則不為素,否則為素。讓乙個清零的計數器sum每找到乙個素就++,直到sum==k時跳出 9樓:化涵桃 不加大括號,for迴圈只執行printf();語句,不會執行break;這一行,迴圈語句的範圍是看括號的範圍的,沒有括號就看它下面出現的第乙個分號(;) 10樓:匿名使用者 你可以通過可執行檔案放在專門的c語言虛擬機器內執行,檢視結果的準確性,你可以呼叫谷歌伺服器電腦系統的api,然後帶入實參,除錯一下程式看看能不能判定它的素數,另外別忘了植入標頭檔案,畫流程圖 11樓:某某知識教授 c語言中判斷n是否為素數可以從2開始到到n-1逐一嘗試,如果可以整除說明不是素數。 根據素數定義,除了1和本身不存在其它約數的正整數為素數。 更進一步,可以從2判斷到n/2或者n的算術平方根,如果不存在約數,那麼即為素數。 12樓:匿名使用者 判斷是不是素數,素數就是只能被1和本身整除的自然數。void main() 13樓:匿名使用者 先來一種比較快速的素數篩選法,這是一種非常高效的篩法,原理的話,你得看下數論方面的書籍#include #include #define maxn 100int flag[maxn+1];int main() for(i=2;i<=maxn;i++) if(!flag[i]) printf("%d ",i); printf("\n"); return 0; }下面的用的是最普通的演算法#include#include #define maxn 100int main()if(j==i) printf("%d ",i);}} printf("\n"); return 0;} 14樓:陳士晟 這是函式的做法 #include void main() int sushu(int a)}} 判斷乙個數是否是素數,為什麼只要除到根號那個數就夠了 ,求c語言** 15樓:匿名使用者 x=ab 那麼a和b,必然有乙個大於√x,乙個小於(或者兩個都等於)。 那麼不是只要判斷到√x就可以麼? c語言中,為什麼可以用平方根判斷素數?請說得詳細點。謝謝! 急!!! 16樓:匿名使用者 你理解錯了。 不是用平方根判斷素數,而是最大取到平方根的整數,可以有效減少迴圈的次數。這個屬於程式的優化。 c語言素數的的判別式疑問 17樓:郝在益 因為在for語句裡,一旦有某乙個數是這個數的因子,那麼就是執行break語句,跳出for迴圈,這個時候,i絕對會<=k的,也就是說這個時候i=k+1,那就證明for語句的所有迴圈都執行到了,也就是沒有執行if語句裡的語句,也就是說在2~~~k之間沒有這個數的因子,那麼,這個數也就是素數了。 滿意請採納!! 18樓:匿名使用者 判別素數的方法舉例來說: 比如這個數m=127,我們在判斷是否素數時需要用i從2開始一直到126的各個整數當作除數計算m/i是否能整除,如果整除了,當前的i就是m的因數從而m就不是素數了,程式中m%i==0就是這個判斷,只不過判斷的是除法的餘數是否為0而已。 在數學上,我們發現沒有必要一定要算2到126做除數這麼多,而只需要算2到根號m(對於m=127,算到11即可得出判斷),所以你會看到迴圈結束條件變成了根號m。這好比你已經判斷了m除以4除不盡,而就可以不去算m除以4的平方16了,也必然除不盡。具體請查數學中對此的解釋。 另外程式中k=sqrt(m);應寫成k=sqrt((double)m); 19樓:蔥蔥發問 你確定程式是對的嗎? break的位置 還有括號 及其亂在k之前如果沒有出現bradk跳轉,那麼k+1 之後就不用測試了它必定是素數。所以i>k+1 if(m%i==0)只是在反覆測試這句 但是你的程式本身應該是有錯誤的。你else錯了。寫的太亂了 沒有邏輯。 20樓: 是這樣的。。。m除以從2到根號m之間的數,如果某一位除斷了,就說明不是素數。當i自增到大於根號m之後還沒有出現除斷的情況,那麼說明m是素數。 素數怎麼判斷!! 21樓:偶夢竹 素數又稱質數。乙個大於1的自然數,除了1和它本身外,不能被其他自然數整除,換句話說就是該數除了1和它本身以外不再有其他的因數。 22樓:庫磬 最簡單方法應是: 乙個自然數a不是2,3,5的倍數時,就用大於或等於7的質數從小到大試除判定 23樓:鞏欣珈藍 質數是指在大於1的自然數中,除了1和它本身以外不再有其他因數的自然數比如5就只能除以五 這就是 可以用在標頭檔案中宣告的pow 函式求,例如 要求a的b次方,就用pow a,b 即可。符號在c中是位異或操作符,不用於求乘方。math 中有函式 pow 可以實現。標頭檔案 include 函式 pow a,b 表示a的b次冪。庫函式 double pow double x,double y 計算... 可以通過字元陣列或字元指標來定義字串,也可以用巨集定義對常量字串進行定義。下面通過舉例來分別進行說明 char str1 helloworld 通過字元陣列來定義字串 helloworld 陣列中每個儲存單元存放乙個字元 char str2 helloworld 通過字元指標來定義字串 hellow... 實參的值傳給了形參,形參可以看著是被調函式中的區域性變數被調函式可有返回值也可以沒有有返回值用return返回。例如int fun int a,int b 主函式呼叫 int a,b,c a 1,b 2 c fun a,b 沒有返回值的函式通常形參都是指標變數,那樣可以直接改變變數的值,例如fun ... 用標準c庫中的字串操作函式就可以了 需要 include string.h 常用的函式有strcpy,strlen,strcmp,strchr,strstr等等 char s ssssabedbewb int len char p s 2 第一種方法 printf 輸入輸入字串的長度 scanf d... rand函式功能為獲取乙個偽隨機數 偽隨機數的概念下面會有介紹 一 函式名 rand 二 宣告 int rand 三 所在標頭檔案 stdlib.h 四 功能 返回乙個偽隨機數。之所以說是偽隨機數,是因為在沒有其它操作下,每次執行同乙個程式,呼叫rand得到的隨機數序列是固定的 不是真正的 隨機 五...C語言中怎麼求冪?c語言中不用庫函式怎麼求冪指數?
C語言中如何定義字串,c語言中,怎麼樣定義乙個字串變數
c語言中的值傳遞是怎麼回事,誰解釋C語言中什麼是值傳遞和位址傳遞??
c語言中怎麼從字串中取字元,C語言中怎樣獲得字串中的單個字元
c語言中rand 函式怎麼用