[問題] 關於 constexpr 質數表

[nevikw39 (☆牜攵☆犬羊)]

開發平台(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
→ loveme00835: 好暴力 xD
→ oToToT: linear sieve呢
演算法筆跡中 linear sieve 是刪掉每個數的質數倍，那我要從什麼開始刪？？

→ loveme00835: 雖然 std::embed() 還沒進, 不過先給你一個提示: 可
→ loveme00835: 以把你的 bool array 轉成 bit array, 然後內嵌在程
→ loveme00835: 式碼裡 https://godbolt.org/z/BhqKza 這樣只要花費
→ loveme00835: 查找的成本就好
→ loveme00835: 一個常見的誤解就是把 constexpr 的求值和物件初始化
→ loveme00835: 時機搞混. 值可以提早在編譯時期求出, 但初始化還是
→ loveme00835: 要在執行時期才能做, 所以除非你可以免去初始化的成
→ loveme00835: 本, 不然 constexpr 能加速的只有那些和物件實例 (in
→ loveme00835: stance) 行為無關的部分
大大的想法有點難懂耶，我再想一下

※ 編輯: nevikw39 (125.227.83.73 臺灣), 04/27/2020 15:04:35
推 stimim: hint: 1e8 內所有的合數必有一個 1e4 以內的質因數
→ stimim: 咦，時限是多少？ 0.6s 過不了嗎？
還想要更快呀

我現在不知道，如何用這 23000 個質數篩出其他質數

※ 編輯: nevikw39 (106.107.240.191 臺灣), 04/27/2020 20:02:15
→ loveme00835: 好好想想: 你建質數表的「目的」是什麼? 手段不是只
→ loveme00835: 有一種
→ stimim: 另外還要看看你現在時間的瓶頸是不是在輸出的部分