欧拉函数:
对正整数n，欧拉函数是少于或等于n的数中与n互质的数的数目。
代码O(sqrt(n)):
ll euler(ll n){
ll ans=n;
for(int i=;i*i<=n;i++){ //这里i*i只是为了减少运算次数，直接i<=n也没错，
if(n%i==){ //因为只有素因子才会加入公式运算。仔细想一下可以明白i*i的用意。
ans=ans/i*(i-);
while(n%i==)
n/=i; //去掉倍数
}
}
if(n>)
ans=ans/n*(n-);
return ans;
}
欧拉线性筛素数
洛谷 P3383 【模板】线性筛素数-线性筛素数(欧拉筛素数)基础题贴个板子备忘
代码改了一点东西O(n):
//线性筛法筛素数(欧拉筛法)
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<bitset>
#include<cassert>
#include<cctype>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<deque>
#include<iomanip>
#include<list>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<vector>
using namespace std;
typedef long long ll; const double PI=acos(-1.0);
const double eps=1e-;
const ll mod=1e9+;
const int inf=0x3f3f3f3f;
const int maxn=2e7+;
const int maxm=+;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); bitset<maxn> is_prime;
int p[maxn],h=; void Prime(int n)
{
is_prime[]=;
is_prime[]=;
for(int i=;i<=n;++i){
if(is_prime[i]==)
p[++h]=i;
for(int j=;j<=h&&p[j]*i<=n;++j){
is_prime[i*p[j]]=;
if(i%p[j]==)
break;
}
}
} int main()
{
int n;
scanf("%d",&n);
Prime(n);
for(int i=;i<=n;i++){
cout<<i<<" ";
cout<<p[i]<<" ";
if(is_prime[i])
printf("No\n");
else
printf("Yes\n");
}
return ;
}
最后传送一下队友的博客: