帐号 自动登录 找回密码 密码 欢迎注册
 搜索

# [讨论] 10秒内计算出1亿素数表, 不输出

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

 无心人 发表于 2013-11-25 21:05 我去看了看Atkin筛的原理，咋感觉不如咱这里讨论的分块筛法呢？ 我实现过Atkin筛法，他不适合分段筛。筛第一块（从1开始）很快，筛接下来块就很慢了。当求很大范围内的素数时，费力不讨好，现实意义不大。

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

 开源我实现的素数筛选法（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) >>

 您需要登录后才可以回帖 登录 | 欢迎注册 本版积分规则 回帖后跳转到最后一页

GMT+8, 2021-7-29 18:14 , Processed in 0.050636 second(s), 15 queries .