原始Atkin筛法来自pocketpy的benchmarks/primes.py1.纯python版本importtimefrommathimportisqrtdefsieve_eratosthenes(limit): 埃拉托斯特尼筛法求素数 返回素数列表 iflimit2:return[]# 初始化布尔数组True表示可能是素数is_prime[True]*(limit1)is_prime[0]is_prime[1]False# 只需筛到 sqrt(limit)foriinrange(2,isqrt(limit)1):ifis_prime[i]:# 从 i*i 开始标记因为更小的倍数已被更小的素数标记过stepi starti*i is_prime[start:limit1:step][False]*((limit-start)//step1)# 收集素数primes[ifori,primeinenumerate(is_prime)ifprime]returnprimesdefsieve_atkin(limit): Atkin筛法求素数 返回素数列表 iflimit2:return[]iflimit2:return[2]iflimit3:return[2,3]# 初始化布尔数组全部设为Falseis_prime[False]*(limit1)# 处理小素数is_prime[2]Trueis_prime[3]True# 三种二次型筛选# 注意代码中使用 x 和 y 的平方小于 limit 的条件与原始Atkin筛法一致limit_sqrtisqrt(limit)forxinrange(1,limit_sqrt1):xxx*xforyinrange(1,limit_sqrt1):yyy*y# 第一种形式: 4x^2 y^2n4*xxyyifnlimitand(n%121orn%125):is_prime[n]notis_prime[n]# 第二种形式: 3x^2 y^2n3*xxyyifnlimitandn%127:is_prime[n]notis_prime[n]# 第三种形式: 3x^2 - y^2n3*xx-yyifxyandnlimitandn%1211:is_prime[n]notis_prime[n]# 移除平方数的倍数forrinrange(5,limit_sqrt1):ifis_prime[r]:rrr*rformultipleinrange(rr,limit1,rr):is_prime[multiple]False# 收集素数primes[ifori,primeinenumerate(is_prime)ifprime]returnprimesdefsum_of_primes(primes_list):计算素数列表的和returnsum(primes_list)defcompare_algorithms(limits): 比较埃拉托斯特尼筛法和Atkin筛法的性能 limits: 要测试的上限列表例如 [1000000, 5000000, 10000000] print(*80)print(f{上限:12}{算法:20}{素数个数:12}{素数总和:20}{耗时(秒):12})print(*80)results{}forlimitinlimits:# 测试埃拉托斯特尼筛法start_timetime.perf_counter()primes_erasieve_eratosthenes(limit)time_eratime.perf_counter()-start_time sum_erasum_of_primes(primes_era)count_eralen(primes_era)# 测试Atkin筛法start_timetime.perf_counter()primes_atkinsieve_atkin(limit)time_atkintime.perf_counter()-start_time sum_atkinsum_of_primes(primes_atkin)count_atkinlen(primes_atkin)# 验证两种算法结果一致assertcount_eracount_atkin,f素数个数不一致:{count_era}vs{count_atkin}assertsum_erasum_atkin,f素数和不一致:{sum_era}vs{sum_atkin}# 存储结果results[limit]{era:{time:time_era,sum:sum_era,count:count_era},atkin:{time:time_atkin,sum:sum_atkin,count:count_atkin}}# 打印结果print(f{limit:12,}{埃拉托斯特尼筛法:20}{count_era:12,}{sum_era:20,}{time_era:12.4f})print(f{limit:12,}{Atkin筛法:20}{count_atkin:12,}{sum_atkin:20,}{time_atkin:12.4f})print(f{:12}{速度比(埃氏筛/Atkin):20}{:12}{:20}{time_era/time_atkin:12.2f}x)print(-*80)returnresultsdefquick_verify():快速验证两种算法的正确性test_limits[100,1000,10000]forlimitintest_limits:primes_erasieve_eratosthenes(limit)primes_atkinsieve_atkin(limit)assertprimes_eraprimes_atkin,f算法结果不一致上限{limit}print(✓ 验证通过埃拉托斯特尼筛法和Atkin筛法结果一致)print()if__name____main__:# 首先验证算法正确性quick_verify()# 定义要测试的上限test_limits[1_000_000,5_000_000,10_000_000]# 100万、500万、1000万# 执行性能比较compare_algorithms(test_limits)执行结果C:\dpython comp_prime.py ✓ 验证通过埃拉托斯特尼筛法和Atkin筛法结果一致 上限 算法 素数个数 素数总和 耗时(秒) 1,000,000 埃拉托斯特尼筛法 78,498 37,550,402,023 0.0385 1,000,000 Atkin筛法 78,498 37,550,402,023 0.1868 速度比(埃氏筛/Atkin) 0.21 x -------------------------------------------------------------------------------- 5,000,000 埃拉托斯特尼筛法 348,513 838,596,693,108 0.2012 5,000,000 Atkin筛法 348,513 838,596,693,108 0.9766 速度比(埃氏筛/Atkin) 0.21 x -------------------------------------------------------------------------------- 10,000,000 埃拉托斯特尼筛法 664,579 3,203,324,994,356 0.4287 10,000,000 Atkin筛法 664,579 3,203,324,994,356 2.0092 速度比(埃氏筛/Atkin) 0.21 x --------------------------------------------------------------------------------2.numpy版本Atkin筛法改为向量化算法埃拉托斯特尼筛法的列表改用np数组。importtimeimportnumpyasnpfrommathimportisqrtdefsieve_atkin_vectorized(limit): 使用NumPy向量化的Atkin筛法求素数 返回素数列表 iflimit2:return[]iflimit2:return[2]iflimit3:return[2,3]# 使用int8类型数组记录翻转次数模2is_primenp.zeros(limit1,dtypenp.int8)is_prime[2]1is_prime[3]1limit_sqrtisqrt(limit)# 创建x和y的网格xnp.arange(1,limit_sqrt1,dtypenp.int32)ynp.arange(1,limit_sqrt1,dtypenp.int32)xxx*x yyy*y# 向量化计算 4x^2 y^2n14*xx[:,np.newaxis]yy[np.newaxis,:]mask1(n1limit)((n1%121)|(n1%125))# 使用bincount统计每个n出现的次数模2counts1np.bincount(n1[mask1],minlengthlimit1)is_prime(is_primecounts1)%2# 向量化计算 3x^2 y^2n23*xx[:,np.newaxis]yy[np.newaxis,:]mask2(n2limit)(n2%127)counts2np.bincount(n2[mask2],minlengthlimit1)is_prime(is_primecounts2)%2# 向量化计算 3x^2 - y^2 (需要 x y)X,Ynp.meshgrid(x,y,indexingij)n33*X*X-Y*Y mask3(XY)(n3limit)(n3%1211)counts3np.bincount(n3[mask3],minlengthlimit1)is_prime(is_primecounts3)%2# 转换为bool数组is_prime_boolis_prime.astype(bool)# 移除平方数的倍数forrinrange(5,limit_sqrt1):ifis_prime_bool[r]:rrr*r is_prime_bool[rr:limit1:rr]False# 收集素数primesnp.where(is_prime_bool)[0].tolist()returnprimesdefsieve_eratosthenes(limit): 埃拉托斯特尼筛法求素数保持原实现 返回素数列表 iflimit2:return[]is_primenp.ones(limit1,dtypebool)is_prime[0:2]Falseforiinrange(2,isqrt(limit)1):ifis_prime[i]:is_prime[i*i:limit1:i]Falseprimesnp.where(is_prime)[0].tolist()returnprimesdefsum_of_primes(primes_list):计算素数列表的和returnsum(primes_list)defcompare_algorithms(limits): 比较埃拉托斯特尼筛法和向量化Atkin筛法的性能 limits: 要测试的上限列表 print(*80)print(f{上限:12}{算法:25}{素数个数:12}{素数总和:20}{耗时(秒):12})print(*80)forlimitinlimits:# 测试埃拉托斯特尼筛法start_timetime.perf_counter()primes_erasieve_eratosthenes(limit)time_eratime.perf_counter()-start_time sum_erasum_of_primes(primes_era)count_eralen(primes_era)# 测试向量化Atkin筛法start_timetime.perf_counter()primes_atkinsieve_atkin_vectorized(limit)time_atkintime.perf_counter()-start_time sum_atkinsum_of_primes(primes_atkin)count_atkinlen(primes_atkin)# 验证结果一致assertcount_eracount_atkin,f素数个数不一致:{count_era}vs{count_atkin}assertsum_erasum_atkin,f素数和不一致:{sum_era}vs{sum_atkin}# 打印结果print(f{limit:12,}{埃拉托斯特尼筛法:25}{count_era:12,}{sum_era:20,}{time_era:12.4f})print(f{limit:12,}{Atkin筛法(向量化):25}{count_atkin:12,}{sum_atkin:20,}{time_atkin:12.4f})print(f{:12}{速度比(埃氏筛/Atkin):25}{:12}{:20}{time_era/time_atkin:12.2f}x)print(-*80)defquick_verify():快速验证向量化Atkin筛法的正确性test_limits[100,1000,10000]forlimitintest_limits:primes_erasieve_eratosthenes(limit)primes_atkinsieve_atkin_vectorized(limit)#print(primes_atkin)assertprimes_eraprimes_atkin,f算法结果不一致上限{limit}print(✓ 验证通过埃拉托斯特尼筛法和向量化Atkin筛法结果一致)print()if__name____main__:# 验证算法正确性quick_verify()# 定义要测试的上限根据内存调整500万可能内存较大test_limits[1_000_000,5_000_000,10_000_000]# 100万、500万# 注意1000万时n1网格约3162x31621000万个元素内存约80MB可以根据机器内存调整# 执行性能比较compare_algorithms(test_limits)执行结果C:\dpython comp_prime2.py ✓ 验证通过埃拉托斯特尼筛法和向量化Atkin筛法结果一致 上限 算法 素数个数 素数总和 耗时(秒) 1,000,000 埃拉托斯特尼筛法 78,498 37,550,402,023 0.0057 1,000,000 Atkin筛法(向量化) 78,498 37,550,402,023 0.0411 速度比(埃氏筛/Atkin) 0.14 x -------------------------------------------------------------------------------- 5,000,000 埃拉托斯特尼筛法 348,513 838,596,693,108 0.0159 5,000,000 Atkin筛法(向量化) 348,513 838,596,693,108 0.1987 速度比(埃氏筛/Atkin) 0.08 x -------------------------------------------------------------------------------- 10,000,000 埃拉托斯特尼筛法 664,579 3,203,324,994,356 0.0283 10,000,000 Atkin筛法(向量化) 664,579 3,203,324,994,356 0.4150 速度比(埃氏筛/Atkin) 0.07 x --------------------------------------------------------------------------------