素数计数函数挑战
2026-08-07 07:19:28
发布于：浙江
73阅读
0回复
0点赞
第一方案：本次使用的原函数是埃氏筛法，时间复杂度
#include <bits/stdc++.h>
using namespace std;
typedef long long ll; // 模板套用宏定义
__attribute__((always_inline)) // 内联亿下
inline int Rate(int res,bool c,int i){ // 步长函数
if(res&1)return c?i<<1:i<<2;
else return c?i<<2:i<<1;
}
vector<pair<int,bool>> PrimeNums(int n){ // 预处理获取 1~sqrt(n)所有素数
if(n<5)return {}; // 没到5返回空数组
int res;
vector<bool> vis((n+1)>>1,0); // 只存奇数，节省空间
vector<pair<int,bool>> a;
for(int i=6;i<x+2;i+=6){ // 等价于i-1<=x
int p1=i-1,p2=i+1;
if(!vis[i>>1]){
a.push_back({p1,0}),res=0;
for(ll j=(ll)p1*p1;j<=n;j+=Rate(res,0,p1),res++)vis[(j+1)>>1]=1; // 不开long long等10^4<=n你就炸了
}
if(p2<=x&&!vis[i>>1+1]){
a.push_back({p2,1}),res=0;
for(ll j=(ll)p2*p2;j<=n;j+=Rate(res,1,p2),res++)vis[(j+1)>>1]=1;
}
}
return a;
}
int prime(int n){ // 主函数：6k±1优化版超级埃氏筛
if(n<2)return 0;
int s=sqrt(n),cnt=0,res;
vector<bool> vis((n+1)>>1,1);
vector<pair<int,bool>> Prime=PrimeNums(s);
for(const auto& i:Prime){ // const auto& 最快
int p1=i.first,res=0;
bool p2=i.second;
for(ll j=(ll)p1*p1;j<=n;j+=Rate(res,p2,p1),res++)vis[(j+1)>>1]=0; // 交替步长 每次“扫”掉的都是6k±1形式的合数
}
for(int i=6;i<n;i+=6)cnt+=vis[i>>1]+vis[(i>>1)+1];
return cnt+(n>1)+(n>2); // 补上2和3
}
int main(){
int n;
cin>>n;
cout<<prime(n);
}
第二方案：本次使用的原函数是埃氏筛法，时间复杂度
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast,inline,omit-frame-pointer,tree-vectorize,tree-slp-vectorize,vect-cost-model=dynamic,ivopts,tree-loop-optimize,tree-loop-distribution,tree-loop-im,tree-loop-ivcanon,loop-interchange,loop-unroll-and-jam,predictive-commoning,tree-dse,tree-fre,tree-sra,tree-ter,tree-copy-prop,tree-ccp,tree-ch,isolate-erroneous-paths,split-loops,split-paths,reassociate,schedule-insns,schedule-insns2,cse-follow-jumps,cse-skip-blocks,gcse-after-reload,gcse-lm,hoist-adjacent-loads,ipa-cp,ipa-cp-clone,ipa-bit-cp,ipa-vrp,ipa-pta,ipa-sra,ipa-icf,ipa-icf-functions,ipa-icf-variables,ipa-profile,ipa-pure-const,ipa-reference,ipa-modref,ipa-jump-function,ipa-devirt,ipa-strlen,fgraphite,fgraphite-identity,floop-nest-optimize,floop-parallelize-all,ftree-parallelize-loops=4,frename-registers,fweb,fira-hoist-pressure,fira-loop-pressure,flto,flto-partition=max,flto-compression-level=9,fuse-linker-plugin,fno-stack-protector,fno-stack-protector-all,fno-stack-check,fno-omit-frame-pointer")
#pragma GCC target("avx512f", "avx512vl", "sse", "sse2", "sse3", "ssse3", "sse4", "sse4.1", "sse4.2", "popcnt", "abm", "mmx", "avx", "avx2", "fma", "bmi", "bmi2", "lzcnt", "tune=native")
typedef long long ll; // 模板套用宏定义
__attribute__((always_inline)) // 内联亿下
inline int Rate(int res,bool c,int i){ // 步长函数
if(res&1)return c?i<<1:i<<2;
else return c?i<<2:i<<1;
}
vector<pair<int,bool>> PrimeNums(int n){ // 预处理递推获取 1~sqrt(n)所有素
if(n<5)return{}; // 递推出口
int s=__builtin_sqrt(n),res;
vector<bool> vis((n+1)>>1,1);
vector<pair<int,bool>> Prime=PrimeNums(s),a;
for(const auto& i:Prime){ // const auto& 最快
int p1=i.first,res=0;
bool p2=i.second;
for(ll j=(ll)p1*p1;j<=n;j+=Rate(res,p2,p1),res++)vis[(j+1)>>1]=0; // 交替步长 每次“扫”掉的都是6k±1形式的合数
}
for(int i=s/6*6+6;i<=n+1;i+=6){
if(vis[i>>1])a.push_back({i-1,0});
if(vis[(i>>1)+1])a.push_back({i+1,1});
}
Prime.reserve(Prime.size()+a.size());
Prime.insert(Prime.end(),a.begin(),a.end());
return Prime;
}
int prime(int n){ // 主函数：超级埃氏筛
if(n<2)return 0;
int s=__builtin_sqrt(n),cnt=0,res;
vector<bool> vis((n+1)>>1,1);
vector<pair<int,bool>> Prime=PrimeNums(s);
for(const auto& i:Prime){
int p1=i.first,res=0;
bool p2=i.second;
for(ll j=(ll)p1*p1;j<=n;j+=Rate(res,p2,p1),res++)vis[(j+1)>>1]=0;
}
for(int i=s/6*6+6;i<=n+1;i+=6)cnt+=vis[i>>1]+vis[(i>>1)+1]; // 直接从Prime后的第一个素数开始
return cnt+Prime.size()+(n>1)+(n>2); // 补上2和3还有1~sqrt(n)的素数个数
}
int main(){
int n;
cin>>n;
cout<<prime(n);
}
看完了我的代码，那我就在这里发起一个挑战：
原函数可以选择埃氏筛、线性筛或分段筛里的一个，可以进行任意的优化（不能用Meissel-Lehmer、Lagarias-Miller-Odlyzko (LMO)、Deleglise-Rivat这三位本身或变体，太超标了，也不能打表），不能用AI，用的是GXX（自己猜）；
挑战方式：{私信、发帖并@我、评论并@我}这三个中的任意一个，需将完整代码放出，我会花时间去写Benchmark（5次1e6 ~ 1e7随机数计时，取5次平均时间对比）对比，将比赛结果（1~3张截图+文字描述）公布。
挑战结果
有帮助，赞一个