作者nevikw39 (☆牜攵☆犬羊)
看板C_and_CPP
标题[问题] 关於 constexpr 质数表
时间Sun Apr 26 23:04:07 2020
开发平台(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://webptt.com/cn.aspx?n=bbs/C_and_CPP/M.1587913453.A.83E.html
1F：→ loveme00835: 好暴力 xD 04/26 23:24
2F：→ oToToT: linear sieve呢 04/26 23:47
演算法笔迹中 linear sieve 是删掉每个数的质数倍，那我要从什麽开始删？？
3F：→ loveme00835: 虽然 std::embed() 还没进, 不过先给你一个提示: 可 04/27 00:15
4F：→ loveme00835: 以把你的 bool array 转成 bit array, 然後内嵌在程 04/27 00:16
6F：→ loveme00835: 查找的成本就好 04/27 00:17
7F：→ loveme00835: 一个常见的误解就是把 constexpr 的求值和物件初始化 04/27 04:31
8F：→ loveme00835: 时机搞混. 值可以提早在编译时期求出, 但初始化还是 04/27 04:31
9F：→ loveme00835: 要在执行时期才能做, 所以除非你可以免去初始化的成 04/27 04:31
10F：→ loveme00835: 本, 不然 constexpr 能加速的只有那些和物件实例 (in 04/27 04:31
11F：→ loveme00835: stance) 行为无关的部分 04/27 04:31
大大的想法有点难懂耶，我再想一下
※ 编辑: nevikw39 (125.227.83.73 台湾), 04/27/2020 15:04:35
12F：推 stimim: hint: 1e8 内所有的合数必有一个 1e4 以内的质因数 04/27 19:26
13F：→ stimim: 咦，时限是多少？ 0.6s 过不了吗？ 04/27 19:35
还想要更快呀
我现在不知道，如何用这 23000 个质数筛出其他质数
※ 编辑: nevikw39 (106.107.240.191 台湾), 04/27/2020 20:02:15
14F：→ loveme00835: 好好想想: 你建质数表的「目的」是什麽? 手段不是只 04/27 20:47
15F：→ loveme00835: 有一种 04/27 20:47
16F：→ stimim: 另外还要看看你现在时间的瓶颈是不是在输出的部分 04/27 22:33