Re: [問題] 新手問質數問題
看板C_and_CPP (C/C++)作者chrisjon (與程式最後的決戰)時間16年前 (2009/09/14 21:07)推噓1(1推 0噓 7→)留言8則, 3人參與討論串3/3 (看更多)
※ 引述《MontaEllis8 (萌塔愛麗絲)》之銘言：
給點建議
: #include <stdio.h>
: #include <stdlib.h>
: int main(void)
: {
: int i,num,prime,flag=0;
: printf("請輸入一個整數: ");
: scanf("%d",&num);
: prime=num-1;
因為質數除了2之外，一定是奇數，如果在這裡先判斷：
如果是2→質數；不是2，但是是2的倍數→跳出；其餘↓
這樣可以跳過所有偶數，僅判斷奇數的輸入值，以省下不少多餘的判斷時間
所以加個判斷是個不錯的選擇
(不過其實不太懂為什麼prime要-1)
: while(flag!=1)
: {
: for(i=2;i<prime;i++)
判斷是否質數，僅需判斷到 1/2 輸入值，如：
101是否是質數 101 / 2 = 50
當判斷到50 101 /50 = 2
其實就已經重覆判斷同一件事，所以僅需判斷到101/2=50即可
判斷到超過50就絕對是質數，可以節省一半的時間。
(例子有點怪怪的，希望你看得懂)
在for上面加個先判斷當i=2時的結果
然後把for內容改成for(i=3;i<prime/2;i=i+2)
因為當i=2會跳出的話，代表不是質數；如果i=2不會跳出，那用i=4也一定不會跳出
: if(prime%i==0) /* not a prime */
: {
: prime--;
先讓prime起始為奇數，在這裡要判斷prime是否為質數，可以改成prime=prime-2;
這樣又可以再節省一半的時間。
: continue;
: }
: flag=1;
: }
: printf("小於%d 的最大質數為%d\n",num,prime);
: system("pause");
: return 0;
: }
參考看看
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 123.195.137.179
推
09/14 21:30, , 1F
09/14 21:30, 1F
→
09/14 21:31, , 2F
09/14 21:31, 2F
→
09/14 21:37, , 3F
09/14 21:37, 3F
→
09/14 21:37, , 4F
09/14 21:37, 4F
→
09/14 21:38, , 5F
09/14 21:38, 5F
→
09/14 22:56, , 6F
09/14 22:56, 6F
→
09/14 22:57, , 7F
09/14 22:57, 7F
→
09/14 22:57, , 8F
09/14 22:57, 8F
討論串 (同標題文章)
C_and_CPP 近期熱門文章
PTT數位生活區 即時熱門文章
