分解质因数模拟:

x=78=2313;
第一次:i=2,将2除尽 ，x=313
第二次：i=3,将3除尽, x=13;
退出，x=13>1即78=3^12^1*13^1;
宏观地看：每除尽一个质因子以后，得到的x中必定没有除掉的这些质因子的因子
代码：

#include<iostream>
using namespace std;
void get(int x)
{
    for(int i=2;i<=x/i;i++)
    {
        if(x%i==0)
        {
            int s=0;
            while(x%i==0)x/=i,s++;
            cout<<i<<' '<<s<<endl;
        }
    }
    if(x>1)cout<<x<<' '<<1<<endl;
    cout<<endl;
}
int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        int a;
        cin>>a;
        get(a);
    }
    return 0;

}

筛质数模拟：st数组表示是否筛出（false则为质数）

方法一：
从 2-n:
若被筛出 continue;
否则 p[cnt++]=i;
选出所有i的倍数st[ki]=true;

模拟：
n=8;
第一次 i=2,p[0]=2, 2,4,6,8被筛出
第二次 i=3,p[1]=3, 3,6被筛出
第三次 i=4,继续
第四次 i==5,p[2]=5,5被筛出
…
第六次 i=7, p[3]=7,7被筛出
这样有的数被重复筛过，时间复杂度较高，
代码：

#include <iostream>
#include <algorithm>

using namespace std;

const int N= 1000010;

int primes[N], cnt;
bool st[N];

void get_primes(int n)
{
    for (int i = 2; i <= n; i ++ )
    {
        if (st[i]) continue;
        primes[cnt ++ ] = i;
        for (int j = i + i; j <= n; j += i)
            st[j] = true;
    }
}

int main()
{
    int n;
    cin >> n;

    get_primes(n);

    cout << cnt << endl;

    return 0;
}

方法二：核心是x仅仅会被最小质因子筛去
从 2-x:
st[i]=false –>p[cnt++]=i;//进质因子
从p数组中找到i的最小质因子将其筛掉(i%p==0)
中途筛掉所有含有其他质因子的数
j=0-n, p[j]<=x/p[i]:
st[p[j]i]=true;
if(i%p[j]==0)break;//找到i的最小质因子
宏观理解：一个合数可以表示位几个质因数指数乘积形式，这也是写p[j]i的原因
1,i%p[j]==0->p[j]是i的最小质因子 p[j]也是p[j]i的最小质因子
2,i%p[j]!=0->还没找到i的最小质因子，p[j]也是p[j]i的最小质因子;
循环结束 p[j]最大就是i,故不用j<=cnt;
代码：

#include<iostream>
using namespace std;
const int N=1000010;
int q[N];
bool st[N];
int cnt;
int get(int n)
{
    for(int i=2;i<=n;i++)
    {
        if(!st[i])q[cnt++]=i;
        for(int j=0;q[j]<=n/i;j++)
        {
            st[q[j]*i]=true;
            if(i%q[j]==0)break;
        }
    }
    return cnt;
}

int main()
{
    int n;
    cin>>n;
    cout<<get(n)<<endl;
    return 0;
}

欧拉函数：即求N的质因子

#include<iostream>
using namespace std;
int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        int a;
        cin>>a;
        long long res=a;
        for(int i=2;i<=a/i;i++)
        {
            if(a%i==0)
            {
                res=res*(i-1)/i;
                while(a%i==0)a/=i;
            }
        }
        if(a>1)res=res*(a-1)/a;
        cout<<res<<endl;
    }
    return 0;
}

筛质数求欧拉函数:求1-n每个数的欧拉函数

问题的关键在于如何将每个数的质因子求出来，可以i从2到n枚举，找到i的最小质因子p[j];
1,i%p[j]=0; phi[ip[j]]=p[j]phi[i];
2,i%p[j]!=0;phi[ip[j]]=(p[j]-1)phi[i];
3，i是质数 p[i]=i-1;
因为所有的合数都可以用筛质数的方法筛出，故可求出所有合数的欧拉函数值，故可以求出所有1-n欧拉函数的值
代码：

#include<iostream>
using namespace std;
typedef long long ll;
ll res;
const int N=1000010;
bool st[N];
int phi[N];
int cnt;
int primes[N];
ll get_euler(int n)
{
    phi[1]=1;
    for(int i=2;i<=n;i++)
    {
        if(!st[i])
        {
            primes[cnt++]=i;
            phi[i]=i-1;
        }
        for(int j=0;primes[j]<=n/i;j++)
        {
            st[primes[j]*i]=true;
            if(i%primes[j]==0)
            {
                phi[i*primes[j]]=phi[i]*primes[j];
                break;
            }
            phi[primes[j]*i]=phi[i]*(primes[j]-1);

        }
    }
    for(int i =1;i<=n;i++)
    {
        res+=phi[i];
    }
    return res;
}
int main()
{
    int n;
    cin>>n;
    cout<<get_euler(n)<<endl;
}