Re: [問題] 新手問質數問題

[chrisjon (與程式最後的決戰)]

※ 引述《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
推 MontaEllis8:想不到我的程式碼有那麼多問題@.@ 其實我才剛看書學
→ MontaEllis8:三天而已 不過還是很感謝各位板友的建議
→ VictorTom:倒不見得有很多問題, 現在只是大家討論一下作法而已:)
→ VictorTom:剛開始學, 有時間的畫還是可以先試著畫簡單的流程圖,
→ VictorTom:把想法圖解後比較容易看出來完整性與實作的流程^^
→ chrisjon:這也是我之前聽到的，如V大所言，先畫個流程圖，再慢慢去
→ chrisjon:修，像我一開始也是像你一樣土法練鋼，寫完再看幾次
→ chrisjon:再跟老板討論時，他就講這樣的一個思考方向