欧拉函数求和问题

问题描述

计算从2到n的欧拉函数和，即计算欧拉函数φ(2) + φ(3) + ... + φ(n)。

方法思路

欧拉函数φ(n)表示小于n且与n互质的正整数的个数。我们需要对每个数i从2到n计算其欧拉函数值，并将这些值累加。

具体步骤如下：

初始化一个数组euler，用于存储每个数的欧拉函数值。

euler[1] = 1，因为1的欧拉函数值为1。

遍历从2到n的每个数i：

如果i不是质数（即euler[i]已被初始化），则继续。

如果i是质数，则对其所有的倍数j进行处理：
- 如果j不是质数（即euler[j]已被初始化），则跳过。
- 否则，euler[j] = j * (1 - 1/p)，其中p是j的质因数。

代码实现

#include #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #define C 0.5772156649#define pi acos(-1.0)#define ll long long#define mod 1000000007#define ls l, m, rt << 1#define rs m + 1, r, rt << 1#pragma comment(linker, "/STACK:1024000000,1024000000")using namespace std;const double g = 10.0, eps = 1e-12;const int N = 1000000 + 10, maxn = 500 + 100, inf = 0x3f3f3f;ll euler[N];void geteuler() { memset(euler, 0, sizeof(euler)); euler[1] = 1; for (int i = 2; i < N; ++i) { if (!euler[i]) { for (int j = i; j < N; j += i) { if (!euler[j]) { euler[j] = j; } euler[j] *= (1 - 1.0 / i); } } }}int main() { ios::sync_with_stdio(false); cin.tie(0); geteuler(); ll n; while (cin >> n) { ll ans = 0; for (ll i = 2; i <= n; ++i) { ans += euler[i]; } cout << ans << endl; }}