本文使用 Zhihu On VSCode 创作并发布
更新:
对于202102180918 ,答案是237406722
题主扩大了数字范围到2*10^{11}
这个数量级,使用线性筛法大约需要100GB左右的内存,使用朴素算法耗时太久,根本跑不出来。因此,考虑使用miller-rabin
算法和分段筛法来计算。我的CPU配置是:9900K [email protected]。编译参数:
g++ -Ofast -march=native -std=c++17
,在我的电脑上,分段筛法只需要30秒就能算出答案。
分段筛法-segSizeRate=4
输出如下:
202102180918
内存占用:4.3MB
used time: 32.464s
answer: 237406722
miller-rabin-64位版本
输出如下:
202102180918
内存占用:忽略不计
used time: 2687.926s
answer: 237406722
2021218918 这个数字数量级不算太大,对于现代计算机来说还是比较好算