欧拉函数（用欧拉筛法求欧拉函数）

873. 欧拉函数

•   题目 
•   提交记录 
•   讨论 
•   题解 
•   视频讲解 

给定 n

个正整数 ai

，请你求出每个数的欧拉函数。

欧拉函数的定义

1∼N

中与 N 互质的数的个数被称为欧拉函数，记为 ϕ(N)。
若在算数基本定理中，N=pa11pa22…pamm，则：
ϕ(N) = N×p1−1p1×p2−1p2×…×pm−1pm

输入格式

第一行包含整数 n

。

接下来 n

行，每行包含一个正整数 ai

。

输出格式

输出共 n

行，每行输出一个正整数 ai

的欧拉函数。

数据范围

1≤n≤100

,
1≤ai≤2×109

输入样例：

3
3
6
8

输出样例：

2
2
4

 * 欧拉函数的定义
 * 1∼N中与 N 互质的数的个数被称为欧拉函数，记为 ϕ(N)。
 * 若在算数基本定理中，N=p1^e1*p2^e2*...*pk^ek;则：
 * phi(N)=N/p1*(p1-1)/p2*(p2-1)/.../pk*(pk-1);

/**
 * 欧拉函数的定义
 * 1∼N中与 N 互质的数的个数被称为欧拉函数，记为 ϕ(N)。
 * 若在算数基本定理中，N=p1^e1*p2^e2*...*pk^ek;则：
 * phi(N)=N/p1*(p1-1)/p2*(p2-1)/.../pk*(pk-1);
*/

#include <iostream>
#include <vector>

using namespace std;

int phi(int v)
{
    int res=v;
    vector<int> vec;
    for(int i=2;i<= v/i;++i)
    {
        if(v%i==0)
        {
            vec.push_back(i);
            while(v%i==0)
                v/=i;
        }
    }
    if(v>1)
        vec.push_back(v);
    
    for(auto a:vec)
        res=res/a*(a-1);
    return res;
}

int main()
{
    int n;
    cin >> n;
    while (n -- )
    {
        int v;
        cin >> v;
        cout << phi(v) << endl;
    }
    return 0;
}

874. 筛法求欧拉函数

•   题目 
•   提交记录 
•   讨论 
•   题解 
•   视频讲解 

给定一个正整数 n

，求 1∼n

中每个数的欧拉函数之和。

输入格式

共一行，包含一个整数 n

。

输出格式

共一行，包含一个整数，表示 1∼n

中每个数的欧拉函数之和。

数据范围

1≤n≤106

输入样例：

6

输出样例：

12

void get_phi(int v)
{
    phi[1]=1;
    for(int i=2;i<=v;++i)
    {
        if(hs[i]==0)
        {
            p[num++]=i;
            phi[i]=i-1; //如果i是质数
        }
        
        for(int j=0;p[j]<=v/i;++j)
        {
            hs[p[j]*i]=1;
            if(i%p[j]==0)
            {
                phi[p[j]*i]=phi[i] * p[j]; //如果p[j]是i的约数，那么p[j]一定是p[j]*i的约数
                break;
            }
            else
                phi[p[j]*i]=phi[i] * (p[j]-1); //如果p[j]不是i的约数，但是p[j]一定是p[j]*i 的约数
        }
    }
}

/**
 * 利用欧拉筛法求质数的过程求1——N的欧拉函数
*/
 
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int maxn=1e6+10;
int p[maxn],num=0,phi[maxn];
bool hs[maxn];

void get_phi(int v)
{
    phi[1]=1;
    for(int i=2;i<=v;++i)
    {
        if(hs[i]==0)
        {
            p[num++]=i;
            phi[i]=i-1; //如果i是质数
        }
        
        for(int j=0;p[j]<=v/i;++j)
        {
            hs[p[j]*i]=1;
            if(i%p[j]==0) 
            {
                phi[p[j]*i]=phi[i] * p[j]; //如果p[j]是i的约数，那么p[j]一定是p[j]*i的约数
                break;
            }
            else
                phi[p[j]*i]=phi[i] * (p[j]-1); //如果p[j]不是i的约数，但是p[j]一定是p[j]*i 的约数
        }
    }
}

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