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

[問題] 關於 constexpr 質數表

看板C_and_CPP (C/C++)作者 (☆牜攵☆犬羊)時間5年前 (2020/04/26 23:04), 5年前編輯推噓1(1推 0噓 15→)
留言16則, 3人參與, 5年前最新討論串1/1
開發平台(Platform): (Ex: Win10, Linux, ...) Ubuntu 編譯器(Ex: GCC, clang, VC++...)+目標環境(跟開發平台不同的話需列出) g++ 7 問題(Question)： 求 1e8 內所有質數。 程式碼(Code)：(請善用置底文網頁, 記得排版，禁止使用圖檔) https://gist.github.com/nevikw39/e9d580c03bf0cf800b03bcf38826608c 補充說明(Supplement)： 一開始我用改良後的篩法，在本機約費時 1.2s、在 judge 0.6s。 我想到利用 constexpr 打好質數表，無奈 loop limit 為 262144，強制提高還會當掉無 法編譯。 所以我想說至少先建好 262144 內的質數表，執行時期再篩。 可是我不曉得在已知這 23000 個質數後，如何最快的求出其他質數。 想請教大家，非常感謝！！ 整天改下來已經頭昏腦脹，如有描述不周的部份我很抱歉 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 106.107.240.191 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/C_and_CPP/M.1587913453.A.83E.html
→
04/26 23:24, 5年前 , 1F
好暴力 xD
04/26 23:24, 1F
→
04/26 23:47, 5年前 , 2F
linear sieve呢
04/26 23:47, 2F
演算法筆跡中 linear sieve 是刪掉每個數的質數倍，那我要從什麼開始刪？？
→
04/27 00:15, 5年前 , 3F
雖然 std::embed() 還沒進, 不過先給你一個提示: 可
04/27 00:15, 3F
→
04/27 00:16, 5年前 , 4F
以把你的 bool array 轉成 bit array, 然後內嵌在程
04/27 00:16, 4F
→
04/27 00:17, 5年前 , 5F
式碼裡 https://godbolt.org/z/BhqKza 這樣只要花費
04/27 00:17, 5F
→
04/27 00:17, 5年前 , 6F
查找的成本就好
04/27 00:17, 6F
→
04/27 04:31, 5年前 , 7F
一個常見的誤解就是把 constexpr 的求值和物件初始化
04/27 04:31, 7F
→
04/27 04:31, 5年前 , 8F
時機搞混. 值可以提早在編譯時期求出, 但初始化還是
04/27 04:31, 8F
→
04/27 04:31, 5年前 , 9F
要在執行時期才能做, 所以除非你可以免去初始化的成
04/27 04:31, 9F
→
04/27 04:31, 5年前 , 10F
本, 不然 constexpr 能加速的只有那些和物件實例 (in
04/27 04:31, 10F
→
04/27 04:31, 5年前 , 11F
stance) 行為無關的部分
04/27 04:31, 11F
大大的想法有點難懂耶，我再想一下 ※ 編輯: nevikw39 (125.227.83.73 臺灣), 04/27/2020 15:04:35
推
04/27 19:26, 5年前 , 12F
hint: 1e8 內所有的合數必有一個 1e4 以內的質因數
04/27 19:26, 12F
→
04/27 19:35, 5年前 , 13F
咦，時限是多少？ 0.6s 過不了嗎？
04/27 19:35, 13F
還想要更快呀 我現在不知道，如何用這 23000 個質數篩出其他質數 ※ 編輯: nevikw39 (106.107.240.191 臺灣), 04/27/2020 20:02:15
→
04/27 20:47, 5年前 , 14F
好好想想: 你建質數表的「目的」是什麼? 手段不是只
04/27 20:47, 14F
→
04/27 20:47, 5年前 , 15F
有一種
04/27 20:47, 15F
→
04/27 22:33, 5年前 , 16F
另外還要看看你現在時間的瓶頸是不是在輸出的部分
04/27 22:33, 16F
‣ 更多 nevikw39 的文章
文章代碼(AID): #1UfQBjW- (C_and_CPP)
C_and_CPP 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 nevikw39 的文章
文章代碼(AID): #1UfQBjW- (C_and_CPP)