欧拉函数线性筛

#include"iostream"
#include"vector"
#include"string.h"
using namespace std;
bool vis[10000];
int phi[10000];
vector<int>prime;
void PHI(int maxn)
{
    memset(vis,1,sizeof(vis));
    phi[1]=1;
    for(int i=2;i<=maxn;i++)
    {
        if(vis[i])
        {
            prime.push_back(i);
            phi[i]=i-1;
        }
        for(int j=0;j<prime.size()&&i*prime[j]<=maxn;j++)
        {
            vis[i*prime[j]]=0;
            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()
{
    PHI(50);
    for(int i=0;i<=50;i++)cout<<"i="<<i<<" "<<phi[i]<<"\n";
}