数论基础--质因数分解

先引入几个基本概念：任何一个合数都至少有一个不大于根号n的素因子（可以用反证法证明一下），并且可以得出结论，如果该数有大于根号N的质因子，那么只能存在一个，这个也可以用反证法证明一下，这就是为什么下面要加上一行（if(n!=1)  cout<<n, 因为此时n是最大的那个大于根号n的质因子）

下面的代码也一并实现了欧拉函数 phi(n)=n*(1-1/p1)*(1-1/p2)*(1-1/p3)...

#include<bits/stdc++.h>
using namespace std;

int main(){
    int n, res;
    cin>>n;
    res=n;
    int cnt=0;
    for(int i=2; i*i<=n; i++){
        if(n%i==0){
            res=res-res/i;
            while(n%i==0){
                ++cnt==1?cout<<i:cout<<"*"<<i;
                n/=i;
            }
        }
    }
    if(n!=1) cout<<"*"<<n;
    cout<<endl;
    cout<<"phi(n)="<<res; 
    
    return 0;
}