[問題] 算質數: 迴圈條件更改就跑出錯的結果

看板C_and_CPP作者 (艾多諾)時間11年前 (2013/06/14 22:18), 編輯推噓3(3推 0噓 65→)
留言68則, 9人參與, 最新討論串1/1
問題(Question)： 起初的的想法是認為第二個FOR迴圈不就簡單用幾個範圍內的數字判斷就好 所以就將for(i = 2; i <= (num/2); i++) 設為for(i = 2; i <= 13; i++) 這樣卻發生了一點問題..... 餵入的資料(Input)： #include <stdio.h> int main() { int i, j, num, prime; for(num=2; num< 1000; num++) { prime = 1; for(i = 2; i <= 13; i++)\*我愚昧的自認為縮小檢驗範圍*\ { if( (num%i) == 0 ) { prime = 0; break; } } if (prime == 1) printf("the prime is %d\n",num); } return 0; } 預期的正確結果(Expected Output)： 列出所有質數 錯誤結果(Wrong Output)： 列出從17開始到1000的質數 補充說明(Supplement)： -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 1.175.167.85
→
06/14 22:20, , 1F
最少要到sqrt(n)啊
06/14 22:20, 1F
我應該修改一下我想問的 我想問的那一段程式語言不是應該會把第一段for迴圈 裡面的數字拿來用第二段for迴圈範圍內的數字(2~13)作驗算 為什麼結果直接從17開始?? ※ 編輯: Idownor 來自: 1.175.167.85 (06/14 22:38)
→
06/14 22:50, , 2F
2~13 的質數在新的內層迴圈會被自己除餘零
06/14 22:50, 2F
謝謝大大的解答，跟我剛剛想的果然一樣!! ※ 編輯: Idownor 來自: 1.175.167.85 (06/14 22:51)
→
06/14 22:58, , 3F
看你這篇讓我想到大一的時候也是覺得到13就好XDDD
06/14 22:58, 3F
→
06/15 00:28, , 4F
對啊, 到 13 的話怎麼去掉 961 = 31 * 31 ?
06/15 00:28, 4F
→
06/15 02:25, , 5F
http://codepad.org/90qDfzlk 我的作法 用兩個變數就夠了
06/15 02:25, 5F
→
06/15 02:27, , 6F
這迴圈也不會有跑多餘的運算 就不需要用到break的功能
06/15 02:27, 6F
→
06/15 02:30, , 7F
對質數的判斷 用的是divisor被累加後所在的位置
06/15 02:30, 7F
→
06/15 03:15, , 8F
一直用 i*i 速度會慢,所以才事先用 sqrt 算過一次。
06/15 03:15, 8F
→
06/15 10:38, , 9F
06/15 10:38, 9F
→
06/15 15:06, , 10F
高手好多,請受小弟一拜
06/15 15:06, 10F
→
06/16 11:58, , 11F
@sardine : 這樣不就又變每次都在loop裡算 sqrt 嗎 @@
06/16 11:58, 11F
→
06/16 11:58, , 12F
我猜有開優化後您寫的兩種方式都會被取代掉,看不出來,不過
06/16 11:58, 12F
→
06/16 11:59, , 13F
跑acm之類的,大多還是會多弄一個變數吧。
06/16 11:59, 13F
→
06/16 15:26, , 14F
底層的loop sqrt是固定的 沒有動作要求sqrt要更動一次
06/16 15:26, 14F
→
06/16 15:27, , 15F
上層的loop x本來就是變數 非變不可呀
06/16 15:27, 15F
推
06/16 15:31, , 16F
在i脫離loop sqrt前 sqrt應該只會被運算一次
06/16 15:31, 16F
→
06/16 15:32, , 17F
下一次的sqrt是在i脫離loop並且x被for重新操作過後
06/16 15:32, 17F
→
06/16 15:45, , 18F
編譯後無論如何都一樣的話 我還是傾向越短越好
06/16 15:45, 18F
→
06/16 15:45, , 19F
以即看的到的變數 越少越好
06/16 15:45, 19F
→
06/16 15:47, , 20F
列質數表在%質數應該會比較快一點點，但是要多用一點記
06/16 15:47, 20F
→
06/16 15:47, , 21F
憶體
06/16 15:47, 21F
推
06/16 15:48, , 22F
這樣寫的希望是善用i++ 無論如何他都是少不了的
06/16 15:48, 22F
→
06/16 15:49, , 23F
tjjh89017 這事我做過 但質數真的超無感..
06/16 15:49, 23F
→
06/16 15:51, , 24F
除非是在大數上 每個運算動作都要多上n倍時 效能才會被
06/16 15:51, 24F
→
06/16 15:51, , 25F
放大n倍
06/16 15:51, 25F
→
06/16 15:52, , 26F
在在基本型態的運算上 就算跑到溢位了 也沒幾秒鐘
06/16 15:52, 26F
推
06/16 16:04, , 27F
sardine那種寫法 照理說內層迴圈每次都要重算sqrt(x) 當
06/16 16:04, 27F
→
06/16 16:06, , 28F
然現在的編譯器都會幫你優化
06/16 16:06, 28F
→
06/16 16:12, , 29F
如果把優化關掉 真的會每次都跑嗎 這樣很有利用的價值
06/16 16:12, 29F
→
06/16 16:13, , 30F
可是要如何測試這件事
06/16 16:13, 30F
→
06/16 16:13, , 31F
編成組語來看
06/16 16:13, 31F
→
06/16 16:16, , 32F
或者你自己寫個有輸出的sqrt()來試試
06/16 16:16, 32F
→
06/16 16:17, , 33F
實際上，很多人都會寫簡碼，但後面都不喜歡這麼寫，原因是
06/16 16:17, 33F
→
06/16 16:18, , 34F
除了以後自己"可能"還要想之外，程式碼還要拿給別人看。
06/16 16:18, 34F
→
06/16 16:18, , 35F
直數超無感?! 改成 1000000 就超有感的吧..... 慢到想哭
06/16 16:18, 35F
→
06/16 16:18, , 36F
質
06/16 16:18, 36F
→
06/16 16:21, , 37F
樓上要不要跑一下 1M 我跑13秒而已
06/16 16:21, 37F
→
06/16 16:22, , 38F
@EdisonX 你真的會覺得這樣很難閱讀嗎
06/16 16:22, 38F
→
06/16 16:23, , 39F
如果真是這樣 我會考慮這樣的意見
06/16 16:23, 39F
→
06/16 16:24, , 40F
"而已" = =
06/16 16:24, 40F
→
06/16 16:24, , 41F
的確是而已阿 還是大家都要求即時反應 要在100ms內這樣
06/16 16:24, 41F
→
06/16 16:29, , 42F
我試了int p=sqrt(x)掛在外面 確實變快了 6s
06/16 16:29, 42F
→
06/16 16:43, , 43F
13 秒還不嫌慢，搞演算法的都要自殺了...
06/16 16:43, 43F
→
06/16 16:44, , 44F
對了，建質數表跑 10M 大概只要 2 秒...
06/16 16:44, 44F
→
06/16 17:17, , 45F
maerdimer 可否提供code讓我拜一下神
06/16 17:17, 45F
→
06/16 17:21, , 46F
是不是到github搜尋prime table之類的字呢?
06/16 17:21, 46F
→
06/16 17:23, , 47F
我只是想知道是用了什麼邏輯把運算法簡化 並且沒有大幅提
06/16 17:23, 47F
→
06/16 17:23, , 48F
升程式碼的複雜度
06/16 17:23, 48F
→
06/16 17:29, , 49F
http://ideone.com/fPDBlz 本機跑 1.2 秒
06/16 17:29, 49F
→
06/16 17:44, , 50F
樓上只print一個數 全部都印完 本機跑54秒..
06/16 17:44, 50F
→
06/16 17:46, , 51F
http://codepad.org/qrGmqfqB 我改你的code有自信贏
06/16 17:46, 51F
→
06/16 17:49, , 52F
砍一半這我也試過 我的機器上沒有差別
06/16 17:49, 52F
→
06/16 17:49, , 53F
抽取陣列的運算過去一直以為會快一些 至少數學上應該少很
06/16 17:49, 53F
→
06/16 17:50, , 54F
算式 但很不幸的 即使用指標來寫 比單一變數用完即印即丟
06/16 17:50, 54F
→
06/16 17:51, , 55F
在我的機器上是輸給了i++的運算
06/16 17:51, 55F
→
06/16 17:51, , 56F
什麼都不印只是老實的把1~n在測試n時全算一次
06/16 17:51, 56F
→
06/16 17:52, , 57F
10M全算完也不用一秒
06/16 17:52, 57F
→
06/16 17:54, , 58F
那就祝福你能把你的機器帶著世界跑了。我退出戰線。
06/16 17:54, 58F
→
06/16 17:56, , 59F
我的電腦都七歲了..
06/16 17:56, 59F
→
06/16 18:06, , 60F
06/16 18:06, 60F
→
06/16 18:19, , 61F
你的 code http://ideone.com/r5isOd 1.51s...
06/16 18:19, 61F
→
06/16 18:26, , 62F
建質數表 http://ideone.com/N7Q6wM 0.03s... 只有 1M
06/16 18:26, 62F
→
06/16 18:33, , 63F
喔..少寫了http://ideone.com/bIivan 這樣才對.....
06/16 18:33, 63F
→
06/16 19:31, , 64F
to sardine: 我建到 10M, 印 700k 個數是 io 慢有什麼好比的
06/16 19:31, 64F
→
06/16 23:16, , 65F
@sardine : 你的 code 不是難看得懂，我的意思是，實際上
06/16 23:16, 65F
→
06/16 23:17, , 66F
在 team work 環境下, "可能" 不是個好選擇。
06/16 23:17, 66F
→
06/16 23:32, , 67F
然後如果你想研究篩法的話....
06/16 23:32, 67F
→
06/16 23:36, , 68F
拿 [2,10億] 做測試 . < 怎麼講一句就斷一次線 XD >
06/16 23:36, 68F
‣ 更多 Idownor 的文章
文章代碼(AID): #1HkoP4hq (C_and_CPP)