欧拉函数O(sqrt(n))与欧拉线性筛素数O(n)总结

欧拉函数:

对正整数n，欧拉函数是少于或等于n的数中与n互质的数的数目。

代码O(sqrt(n)):

 1 ll euler(ll n){                                   
 2     ll ans=n;
 3     for(int i=2;i*i<=n;i++){                     //这里i*i只是为了减少运算次数，直接i<=n也没错，
 4         if(n%i==0){                              //因为只有素因子才会加入公式运算。仔细想一下可以明白i*i的用意。
 5             ans=ans/i*(i-1);
 6             while(n%i==0)
 7                 n/=i;                            //去掉倍数
 8         }
 9     }
10     if(n>1)
11         ans=ans/n*(n-1);
12     return ans;
13 }

欧拉线性筛素数

洛谷 P3383 【模板】线性筛素数-线性筛素数(欧拉筛素数)基础题贴个板子备忘

代码改了一点东西O(n):

 1 //线性筛法筛素数(欧拉筛法)
 2 #include<iostream>
 3 #include<cstdio>
 4 #include<cstring>
 5 #include<algorithm>
 6 #include<bitset>
 7 #include<cassert>
 8 #include<cctype>
 9 #include<cmath>
10 #include<cstdlib>
11 #include<ctime>
12 #include<deque>
13 #include<iomanip>
14 #include<list>
15 #include<map>
16 #include<queue>
17 #include<set>
18 #include<stack>
19 #include<vector>
20 using namespace std;
21 typedef long long ll;
22 
23 const double PI=acos(-1.0);
24 const double eps=1e-6;
25 const ll mod=1e9+7;
26 const int inf=0x3f3f3f3f;
27 const int maxn=2e7+10;
28 const int maxm=100+10;
29 #define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
30 
31 bitset<maxn> is_prime;
32 int p[maxn],h=0;
33 
34 void Prime(int n)
35 {
36     is_prime[0]=1;
37     is_prime[1]=1;
38     for(int i=2;i<=n;++i){
39         if(is_prime[i]==0)
40             p[++h]=i;
41         for(int j=1;j<=h&&p[j]*i<=n;++j){
42             is_prime[i*p[j]]=1;
43             if(i%p[j]==0)
44                 break;
45         }
46     }
47 }
48 
49 int main()
50 {
51     int n;
52     scanf("%d",&n);
53     Prime(n);
54     for(int i=1;i<=n;i++){
55         cout<<i<<" ";
56         cout<<p[i]<<" ";
57         if(is_prime[i])
58             printf("No
");
59         else
60             printf("Yes
");
61     }
62     return 0;
63 }

最后传送一下队友的博客:

欧拉函数总结