10秒内计算出1亿素数表, 不输出

kastin

目前应该是这篇论文中的算法效率最高的吧，谁能用c++实现这个算法呢？感觉后半部分有些复杂。
M. DELEGLISE & J. RIVAT， COMPUTING PI (x) THE MEISSEL, LEHMER, LAGARIAS,MILLER, ODLYZKO METHOD。

liangbch

无心人 发表于 2013-11-25 21:05
我去看了看Atkin筛的原理，咋感觉不如咱这里讨论的分块筛法呢？

我实现过Atkin筛法，他不适合分段筛。筛第一块（从1开始）很快，筛接下来块就很慢了。当求很大范围内的素数时，费力不讨好，现实意义不大。

Tuberose

计算质数/素数的最快的方法是：PrimeSieve
http://primesieve.org/
一亿的只是毫秒计
开源的

tprime

开源我实现的素数筛选法（n<2^64） https://github.com/ktprime/ktprime/blob/master/PrimeNumber.cpp
单线程性能和primesieve https://github.com/kimwalisch/primesieve 相当

Intel(R) Core(TM) i7-7500U CPU @ 2.70GHz
cache_level 1, cache_type = 1 cache_size = 32 kb
cache_level 1, cache_type = 2 cache_size = 32 kb
cache_level 2, cache_type = 3 cache_size = 256 kb
cache_level 3, cache_type = 3 cache_size = 4096 kb L1Dsize/L2Size/L3Size = 32/256/4096 kb, cores = 4

pi(1e9) = 50847534 (0.00 + 0.14 = 0.14 sec 2048 kb L228 8)
pi(1e12,+1e10) = 361840208 (0.00 + 2.56 = 2.56 sec 2048 kb L228 8)
pi(1e14,+1e10) = 310208140 (0.01 + 3.67 = 3.69 sec 2048 kb L228 8)
pi(1e10) = 455052511 (0.00 + 1.64 = 1.64 sec 2048 kb L228 8)
pi(1e12,+1e9) = 36190991 (0.00 + 0.25 = 0.25 sec 2048 kb L228 8)
pi(1e16,+1e9) = 27153205 (0.08 + 0.50 = 0.58 sec 2048 kb L228 8)
pi(1e18,+1e9) = 24127085 (0.97 + 0.62 = 1.59 sec 2048 kb L228 8)
------------------------------------------------------------------------------------------------------------
Fast implementation of the segmented sieve of Eratosthenes n < 2^64
Copyright (C) by 2010-2020 Huang Yuanbing 22738078@qq.com/bailuzhou@163.com
Compile: g++ -march=native -funroll-loops -O3 -pipe PrimeNumber.cpp -o prime

Compiled by gcc 10.2.0 __cplusplus = 201703 x86-64 16:32:32 Oct  4 2020 in PrimeNumber99.cpp
[MARCO] : MEM_WHEEL = 4 mb, WHEEL_SIZE = 16 kb, SIEVE_SIZE = 2048 kb, WHEEL/WH210 = 30/210
[CACHE] : L1Size = 32, L2Size = 256, SieveSize = 2048, Bucket = 1273, Block = 14080
[ARGS ] : L1Segs/L2Segs/Mseg/Bsegs = (2,2,8,8)
[ARGS ] : L1Maxp/L2Maxp/L3Maxp/Medium/Large/SieveSize = (17011,131101,10485761,7864500,999999999,2097152)
------------------------------------------------------------------------------------------------------------
>> e10
pi(1e10) = 455052511 (0.00 + 1.64 = 1.64 sec 2048 kb L228 8)
>> e18 e9
pi(1e18,+1e9) = 24127085 (0.91 + 0.64 = 1.55 sec 2048 kb L228 8)
>>