本文使用 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 這個數位數量級不算太大,對於現代電腦來說還是比較好算