线性筛
int prime[maxl]; bool mark[maxl]; int tot; inline void oula() { for(int i=2;i<=maxl;i++) { if(!mark[i])prime[++tot]=i; for(int j=1;j<=tot and i+prime[j]<=maxl;j++){ mark[i*prime[j]]=1; if(i%prime[j]==0)break; } } }
最后一行代码是为了保证不重复。
可以顺便求欧拉函数的φ值。欧拉函数的值φx是x以内与x互素的数的个数。φ是积性函数,性质如下:
若n是素数,φn=n-1。
若n是质数p的k次幂:
φn=pk-pk-1=(p-1)pk-1
若m与n互质:
φ(mn)=φm*φn
若要求单个数的phi值:
#include<iostream> #include<cstdio> #include<cmath> #define ll long long using namespace std; ll n,ans; int m; ll phi(ll x) { ll t=x; for(ll i=2;i<=m;i++) if(x%i==0) { t=t/i*(i-1); while(x%i==0)x/=i; } if(x>1)t=t/x*(x-1); return t; } int main() { scanf("%lld",&n); m=sqrt(n); for(int i=1;i<=m;i++) if(n%i==0) { ans+=(ll)i*phi(n/i); if(i*i<n)ans+=(ll)(n/i)*phi(i); } printf("%lld",ans); return 0; }
如要算出范围内所有的phi值:
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> using namespace std; typedef long long ll; const int maxn=1e8; inline int read() { int x=0;char c=getchar(); while(!isdigit(c))c=getchar(); while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar(); return x; } int phi[maxn],prime[maxn>>1],tot,n,ans; bool mark[maxn]; inline void oula() { phi[1]=1; for(int i=2;i<=n;i++) { if(!mark[i]) { prime[++tot]=i; phi[i]=i-1; } for(int j=1;j<=tot and i*prime[j]<=n;j++) { mark[i*prime[j]]=1; if(i%prime[j]==0)phi[i*prime[j]]=phi[i]*prime[j]; else phi[i*prime[j]]=phi[i]*(prime[j]-1);
if(i%prime[j])break; } } } int main() { n=read();
int m=read(); oula(); while(m--)printf("%d ",prime[read()]); return 0; }
注意φ1=1.