数学研发论坛

 找回密码
 欢迎注册
楼主: 无心人

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

[复制链接]
发表于 2013-11-28 23:25:18 | 显示全部楼层
目前应该是这篇论文中的算法效率最高的吧,谁能用c++实现这个算法呢?感觉后半部分有些复杂。
M. DELEGLISE & J. RIVAT, COMPUTING PI (x) THE MEISSEL, LEHMER, LAGARIAS,MILLER, ODLYZKO METHOD。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2013-11-29 13:54:30 | 显示全部楼层
无心人 发表于 2013-11-25 21:05
我去看了看Atkin筛的原理,咋感觉不如咱这里讨论的分块筛法呢?

我实现过Atkin筛法,他不适合分段筛。筛第一块(从1开始)很快,筛接下来块就很慢了。当求很大范围内的素数时,费力不讨好,现实意义不大。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2015-4-14 17:27:10 | 显示全部楼层
计算质数/素数的最快的方法是:PrimeSieve
http://primesieve.org/
一亿的只是毫秒计
开源的
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2020-10-4 19:52:45 | 显示全部楼层
开源我实现的素数筛选法(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)
>>
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2020-12-2 18:29 , Processed in 0.078589 second(s), 15 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表