欧拉筛，O（线性） 

考虑三个地方，即可筛出积性函数f(x):

1.x为素数

2.p不整除于x 

3.p整除于x(break)

#include
     
      #define MAXN 200000using namespace std;int prime[MAXN];bool istprime[MAXN];void makePrime(int num){    int cnt=0;    istprime[1]=1;    for(int i=2;i<=num;i++){        if(!istprime[i])  prime[++cnt]=i;        for(int j=1;prime[j]*i<=num&&j<=cnt;j++){            istprime[i*prime[j]]=1;            if(i%prime[j]==0) break;        }    }}int main(){    int n;    cin>>n;    makePrime(n);    for(int i=1;i<=n;i++) if(!istprime[i]) cout<
      <<" ";}
     

 

• [x] 唯一分解定理 有素数表复杂度在lnn，没有则sqrt(n)

• [x] 威尔逊定理 

• [x] 费马小定理

• 设p为素数，a为正整数，若GCD(p,a)==1,则a^(p-1)≡1 MOD p

欧拉函数

1. 若p为素数，则E(p)=p-1;

2. E(p)<=p-1,当且仅当p为素数取等号;

3. E为积性函数

4. 若n=p1^α1 * p2^α2 * … pk^αk，则有E(n)=n(1-1/p1)(1-1/p2)…(1-1/pn);

线性筛欧拉函数表（略加改动的线性筛素数）

//Writer:GhostCai && His Yellow Duck#include
    
     #define MAXN 200000using namespace std;int prime[MAXN];bool istprime[MAXN];int phi[MAXN];void makePrime(int num){    int cnt=0;    phi[1]=1;    for(int i=2;i<=num;i++){        if(!istprime[i])  prime[++cnt]=i,phi[i]=i-1;        for(int j=1;prime[j]*i<=num&&j<=cnt;j++){            istprime[i*prime[j]]=1;            if(i%prime[j]==0) {                phi[i*prime[j]]=phi[i]*prime[j];                break;            }            else phi[i*prime[j]]=phi[i]*(prime[j]-1);        }    }}int main(){    int n;    cin>>n;    makePrime(n);    for(int i=1;i<=n;i++) cout<
     <<" "<
      
       <
      
    

• [ ] 欧拉定理
• [x] Miller-Rabin素数测试
• [ ] Pollard Rho算法