算法基础之筛法求欧拉函数

筛法求欧拉函数

• 核心思想 ：线性筛法 筛的过程中顺便求欧拉函数

  • 第一种情况 (i % prime[j] == 0)

    • 

  • 第二种情况 (i % prime[j] != 0)

    • 

  •   #include<iostream>
      #include<algorithm>
      
      using namespace std;
      typedef long long LL;
      const int N = 1000010;
      
      int prime[N],cnt;
      bool st[N];
      int euler[N];  //欧拉函数
      
      void get_euler(int n)
      {
          euler[1] = 1;
          for(int i =2;i<= n;i++)
          {
              if(!st[i]) 
              {
                  prime[cnt++] = i;
                  euler[i] = i-1;  //如果是质数 互质的数就是1~i-1
              }
              for(int j=0;prime[j]<= n/i;j++)
              {
                  int t = prime[j] *i;
                  st[t] = true;
                  if(i % prime[j] == 0)  //第一种情况
                  {
                      euler[t] = euler[i] * prime[j];
                      break;
                  }
                  euler[t] = euler[i] * (prime[j] - 1);  //第二种情况
              }
          }
      }
      
      int main()
      {
          int n;
          cin>>n;
          
          get_euler(n);
          
          LL res = 0;
          
          for(int i=1;i<=n;i++) res +=euler[i];
          
          cout<<res;
      }