PTT數位生活區 / C_and_CPP (C/C++)

[問題] 老梗的質數問題 (已解決)

看板C_and_CPP (C/C++)作者 (Cory)時間15年前 (2011/06/05 22:16), 編輯推噓6(6推 0噓 22→)
留言28則, 8人參與, 最新討論串1/1
Code: http://pastie.org/2022517 老梗的質數問題 因為數字稍大 (1,000,000) 所以必須盡量有效率點 經過爬文後 已經優化的部分如下: 1. 建立質數表,滿足題目多次查詢的需求 2. 迴圈變化 i=i+2 砍掉2的倍數 3. 只使用質數表內的質數驗證 4. 用 x*x > i 取代 x > sqrt(i) 減少運算複雜度 5. cin / cout 改成 printf / scanf 加快讀寫速度 目前單純跑質數表是 0.35 秒 應該不算太慢 但是題目有點機車 會餵大量的數字 導致最後都會超過 1 秒的時間限制 (數字小量就可以AC) 所以想請教各位 這樣的算法還是否能改進 ?? 或是說直接重寫成 "刪去法" 會比較好呢 ? 還是根本是我們老師弄的 Online Judge 設計不良 ? (目前無人通過) 以上 感謝各位的協助~ -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 111.255.233.233
→
06/05 22:43, , 1F
質數表建完後用 binary search 查是不是質數
06/05 22:43, 1F
恩 來研究一下好了 (小弟新手)
→
06/05 22:45, , 2F
同樓上, 全找出來試試
06/05 22:45, 2F
→
06/05 22:46, , 3F
都有 prime_v 了，連 binary search 都不用才對
06/05 22:46, 3F
用 二分搜尋法 去找 好像比較快的樣子 ?
→
06/05 22:47, , 4F
疑, 沒看到 XD
06/05 22:47, 4F
→
06/05 22:49, , 5F
if(prime_v[i]*prime_v[i]>k) break; 改掉先用一個變
06/05 22:49, 5F
→
06/05 22:49, , 6F
數存k開根號的結果, 直接prime_v[i]跟root_of_k比
06/05 22:49, 6F
剛剛改了~但是效果好像不明顯
→
06/05 22:55, , 7F
能改進的其實還很多 :p
06/05 22:55, 7F
煩請煩高手指點了
→
06/05 22:55, , 8F
inner loop跑的次數太多了, 到root_of_k就好, 不要把
06/05 22:55, 8F
→
06/05 22:56, , 9F
所有輸入都存起來, 每讀一個馬上輸出結果就好
06/05 22:56, 9F
可是題目規定要先全部輸入再輸出 ※ 編輯: cory8249 來自: 111.255.233.233 (06/05 23:13)
→
06/05 23:10, , 10F
才10^6而已 就用Eratosthenes篩法就好了呀
06/05 23:10, 10F
恩 那我重寫一個試試看好了
→
06/05 23:14, , 11F
除非它是測你輸入的時間點跟輸出時間點, 否則都是用IO
06/05 23:14, 11F
→
06/05 23:15, , 12F
重導向, 最後程式結束作檔案比對而已
06/05 23:15, 12F
原來如此... 恕小弟無知 >"< ※ 編輯: cory8249 來自: 111.255.233.233 (06/05 23:26) ※ 編輯: cory8249 來自: 111.255.233.233 (06/05 23:27)
推
06/05 23:27, , 13F
開一個 1000001 的陣列, 把質數對應的項目標示出來
06/05 23:27, 13F
→
06/05 23:28, , 14F
這樣對於每個詢問 直接查詢對應的項目是否有被標記就好
06/05 23:28, 14F
→
06/05 23:29, , 15F
樓上說的像是: bool is_prime[1000001]; [0] [1]不用
06/05 23:29, 15F
終於AC了 !! 非常感謝各位的幫忙 ※ 編輯: cory8249 來自: 111.255.233.233 (06/05 23:46)
推
06/06 02:38, , 16F
>> 用 x*x > i 取代 x > sqrt(i)
06/06 02:38, 16F
→
06/06 02:38, , 17F
沒人懷疑過這點嗎?這部份我實際上傳是較慢的.
06/06 02:38, 17F
→
06/06 02:39, , 18F
最後是用 target = (int)ceil(sqrt((double)x)));
06/06 02:39, 18F
→
06/06 11:29, , 19F
篩法：git://gist.github.com/1009686.git
06/06 11:29, 19F
→
06/06 11:31, , 20F
其實我覺得改那部份不會快多少@@
06/06 11:31, 20F
→
06/06 11:31, , 21F
x*x>i的部份
06/06 11:31, 21F
推
06/07 01:32, , 22F
大數字用 Miller-Rabin test 測 2 7 61 XD 神速
06/07 01:32, 22F
→
06/07 01:32, , 23F
Miller-Rabin test http://tinyurl.com/3pmvojz
06/07 01:32, 23F
→
06/07 18:46, , 24F
回yoco大 樓上的wiki似乎被砍掉了@@
06/07 18:46, 24F
推
06/07 22:34, , 25F
Miller-Rabin, 拙著 : http://ppt.cc/oneJ
06/07 22:34, 25F
推
06/08 00:20, , 26F
可以直接完算78500個質數塞進source code嗎XD?
06/08 00:20, 26F
→
06/08 07:12, , 27F
@cole945: stack 恐沒那麼大可以塞
06/08 07:12, 27F
推
06/09 02:23, , 28F
塞global呀. 而且原本的prime_v就已經是local變數了呀 囧
06/09 02:23, 28F
‣ 更多 cory8249 的文章
文章代碼(AID): #1Dwu_GS3 (C_and_CPP)
C_and_CPP 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 cory8249 的文章
文章代碼(AID): #1Dwu_GS3 (C_and_CPP)